POJ – 1821 单调队列优化DP

题意:n个墙壁m个粉刷匠,每个墙壁至多能被刷一次,每个粉刷匠要么不刷,要么就粉刷包含第Si块的长度不超过Li的连续墙壁(中间可不刷),每一块被刷的墙壁都可获得Pi的利润,求最大利润

避免重复粉刷:

首先对Si排序并定义$f[i][j]$:前i个木匠处理到第j块木板时的最大利润

此时[j+1,n]保证没被处理以满足无后效性

保证情况一的合法

$f[i][j]=f[i-1][j]$

保证情况二的Si必须被粉刷

定义处理的区间为[k+1,j]

则$f[i][j]=max_kf[i-1][k]+P_i*(j-k)$

此时要求Si必须在[k+1,j]内部,则对k加以限定:$k+1≤S_i≤j$

连续长度的表示:$j-k≤L_i$

中间可空出部分的表示$f[i][j]=f[i][j-1]$

由此可总结转移方程的三部分

前两部分为 $f[i][j]=max(f[i-1][j],f[i][j-1])$

最后一部分为$f[i][j]=max_{j-L_i≤k≤S_i-1}f[i-1][k]+P_i*(j-k),S_i≤j$

对于第三部分可改写方程为$f[i][j]=max_{j-L_i≤k≤S_i-1}(f[i-1][k]-kP_i)+jP_i,S_i≤j$以满足单调队列优化

单调队列在$i$的内循环当中可认为$i$是常数,也就是说每一层$i$都需要设立一个只与$k$有关的单调队列$que$,但在实际中只使用一个

$que$每一次的初始化范围由最小的$j$决定 由$S_i≤j$和$j-L_i≤k≤S_i-1$

得$S_i-L_i≤k_{init}≤S_i-1$

此时$j=1$则得到所有有效的状态$k$

更新过程保证头部$val$最优,$k$单调递增(因为后者的更新顺序是从左往右)

注意单调更新时只对头部更新,因为单调范围右边界总是$S_i-1$

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iter(i,j) for(int i=0;i<(j).size();i++)
#define print(a) printf("%lld",(ll)a)
#define println(a) printf("%lld\n",(ll)a)
#define printbk(a) printf("%lld ",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int MAXN = 2e4+11;
const int oo = 0x3f3f3f3f;
typedef long long ll;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct XJB{
    int l,p,s;
    bool operator < (const XJB &r) const{
        return s<r.s;
    }
}a[MAXN];
int n,m;
int f[233][MAXN];
inline int cal(int i,int k){
    return f[i-1][k]-a[i].p*k;
}
int main(){
    while(cin>>n>>m){
        rep(i,1,m){
            a[i].l=read();
            a[i].p=read();
            a[i].s=read();
        }
        sort(a+1,a+1+m);
        memset(f,0,sizeof f);
        deque<int> que;
        rep(i,1,m){
            while(!que.empty()) que.pop_back();
            rep(k,max(0,a[i].s-a[i].l),a[i].s-1){ //j-Li<=k<=Si-1,j>=Si
                while(!que.empty()&&cal(i,k)>=cal(i,que.back())) que.pop_back();
                que.push_back(k);
            }
            rep(j,1,n){
                f[i][j]=max(f[i-1][j],f[i][j-1]);
                if(j>=a[i].s){
                    while(!que.empty()&&que.front()<j-a[i].l) que.pop_front();
                    if(!que.empty()) f[i][j]=max(f[i][j],cal(i,que.front())+a[i].p*j);
                }
            }
        }
        println(f[m][n]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注