POJ1821Fence题解

Huanle · 2019-10-30 17:37:49 · 个人记录

一道简单的单调队列优化DP的题目，需要注意一个小细节：决策集合的范围是k<j-L[i],而不是k<=j-L[i]，失之毫厘，差之千里，这再次让我感受到了动态规划的精细和精妙。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=(int)2e4+10;
int n,m,f[N],g[N],q[N];
struct Node{
    int L,P,S;
    bool operator<(const Node &Rhs)const{
        return S<Rhs.S;
    }
}a[105];
int main(){
    freopen("a.in","r",stdin);freopen("a.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].L,&a[i].P,&a[i].S);
    sort(a+1,a+1+m);
    for(int i=1,l,r;i<=m;i++){
        for(int j=1;j<=n;j++)g[j]=f[j],f[j]=0;
        q[l=r=1]=0;
        for(int j=1;j<=n;j++){
            f[j]=max(f[j-1],g[j]);
            if(a[i].S<=j&&j<a[i].S+a[i].L){
                while(l<r&&q[l]<j-a[i].L)l++;
                f[j]=max(f[j],g[q[l]]+(j-q[l])*a[i].P);
            }
            else if(j<a[i].S){
                while(l<=r&&g[q[r]]-a[i].P*q[r]<=g[j]-a[i].P*j)r--;
                q[++r]=j;
            }
                /*for(int k=max(j-a[i].L,0);k<a[i].S;k++)
                    f[i][j]=max(f[i][j],f[i-1][k]+(j-k)*a[i].P);*/
        }
    }
    cout<<f[n]<<endl;
    return 0;
}