「题解」围栏 Fence(未完待续:题目链接、题目、题解)

题目链接:POJ 1821/AcWing 298

题目

题解

代码

#include<cstdio>
#include<algorithm>
using std::max;
using std::sort;
#include<deque>
using std::deque;
const int MAXN=16000+5;
const int MAXM=100+5;
const int MAXP=10000+5;
struct Node{
    int l,p,s;
    void Read(void){
        scanf("%d%d%d",&l,&p,&s);
        return;
    }
    bool operator<(const Node &a)const{
        return s<a.s;
    }
};
int n,m;
int f[MAXM][MAXN];
Node a[MAXM];
deque<int> Q;
int Calc(int,int);
int main(void){
    register int i,j,k;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        a[i].Read();
    sort(a+1,a+m+1);
    for(i=1;i<=m;++i){
        Q.clear();
        for(k=max(0,a[i].s-a[i].l);k<a[i].s;++k){
            while(!Q.empty()&&Calc(i,Q.back())<=Calc(i,k))
                Q.pop_back();
            Q.push_back((int)k);
        }
        for(j=1;j<=n;++j){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(j>=a[i].s){
                while(!Q.empty()&&Q.front()<j-a[i].l)
                    Q.pop_front();
                if(!Q.empty())
                    f[i][j]=max(f[i][j],Calc(i,Q.front())+a[i].p*j);
            }
        }
    }
    printf("%d\n",f[m][n]);
    return 0;
}
int Calc(int i,int k){
    return f[i-1][k]-a[i].p*k;
}