2019-02-16

单调队列优化dp

dp优化

poj1821

题意

有若干个工人，他们要粉刷一个栅栏。第$i$个工人若要粉刷墙面，那么他必须刷连续的若干段，且块数不能超过$L_i$,每刷一块都会获得$P_i$的报酬。问如何粉刷，使得工人的薪酬最大。

题解

设$F[i, j]$表示的是前i个工人粉刷j面墙的总的薪酬。

那么转态转移方程可以列出来。

若第i个工人不粉刷墙面，那么转态转移为：

$F[i, j] = F[i-1, j]$

若第i个人粉刷墙面，那么必须找到一个点从前i-1个人转移而来。

因为有粉刷的块数的限制，所以$j-L_i<k$

且$k<=S_i-1$, $S_i表示的是开始刷的序号$

$F[i, j] = max_{j-L_i<k\le s_i-1}(F[i-1, k]+(j-k)*P_i)$

若用暴力进行求解，那么第一层循环是人，第二层循环是木板的序号，第三层循环找决策点。

时间复杂度为$O(mn^2)$

我们对其进行相应的决策点的优化。

我们观察，当j+1后，k的上界是保持不变的，下界是+1的增大。

那么我们能不能保存中间的决策最优值，从而降低相应的时间复杂度。

$F[i, j] = max((F[i-1, k]-kP_i) +jP_i)$

第一部分和k有关，第二部分和j有关

由于是找最大值，我们就建立一个单调队列，来找最优的答案。

基本的思路：

排除上一次的不优的决策点
加入新的决策点
看队列头部的决策点是否符合长度为$L_i$的要求
更新答案

ac code

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 16000+10;
const int maxm = 110;
int dp[maxm][maxn];
struct Node{
    int l, s, p;
    bool operator < (const Node b) const{
        return s<b.s;
    }
}node[maxm];
int calc(int i, int j){
    return dp[i-1][j]-j*node[i].p;
}
//保存着k变量的决策点。
int q[maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) scanf("%d%d%d", &node[i].l, &node[i].p, &node[i].s);
    sort(node+1, node+1+m);
    for(int i=1; i<=m; i++){
        int l=1, r=0;
        for(int k=max(0, node[i].s-node[i].l); k<=node[i].s-1; k++){
            while(l<=r && calc(i, q[r])<=calc(i, k)) r--;
            q[++r] = k;
        }
        for(int j=1; j<=n; j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(j>=node[i].s){
                while(l<=r&&q[l]<j-node[i].l) l++;
                if(l<=r) dp[i][j] = max(dp[i][j], calc(i, q[l])+node[i].p*j);
            }
        }
    }
    printf("%d\n", dp[m][n]);
    return 0;
}

未解决的问题

本文标题:单调队列优化dp

文章作者:Babydragon

发布时间:2019-02-16, 14:01:05

最后更新:2019-02-16, 14:46:13

原始链接:http://baolintian.github.io/2019/02/16/单调队列优化dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。