Fence

Fence

有一个长度为n的\([1,n]\)墙，有k位工人，第i位工人有参数\(s_i,p_i,l_i\)，意思该位工人可以刷包含\(s_i\)的长度小于等于\(l_i\)的区间，报酬为区间长度乘以\(p_i\)，墙的一个位置不能被重复刷，问最大的报酬之和，\(1 <= n <= 16 000,1 <= k <= 100\)

解

注意到k * n才十万，不难想到设\(f[i][j]\)表示前i位工人刷前j个位置的最大报酬之和，注意到我们要保证递推的无后效性，于是我们得把工人的\(s_i\)排序，因此有

\[f[i][j]=\max(f[i-1][j],f[i][j-1],\max_{j-l_i\leq k\leq s_i}f[i-1][k]+(j-k)\times p_i)\]

注意到在i一定时，决策范围都是呈单调性，且j与k无关，于是可以使用单调队列优化，注意判边界即可，时间复杂度\(O(nk)\)。

参考代码：

#include <iostream>
#include <cstdio>
#include <deque>
#include <algorithm>
#define il inline
#define ri register
using namespace std;
il void read(int&);
struct pi{
    int x,y;
};
struct worker{
    int l,p,s;
    il bool operator<(const worker&x)const{
        return s<x.s;
    }
    il void read(){
        ::read(l),::read(p),::read(s);
    }
}w[110];
deque<pi>D;
int dp[110][16010];
template<class free>il free Max(free,free);
int main(){
    int n,k;read(n),read(k);
    for(int i(1);i<=k;++i)w[i].read();
    sort(w+1,w+k+1);
    for(int i(1);i<=k;++i){
        D.clear();
        for(int j(0);j<=n;++j){
            while(D.size()&&j-D.front().y>w[i].l)D.pop_front();
            dp[i][j]=Max(dp[i-1][j],dp[i][j-1]);
            if(D.size()&&j>=w[i].s)dp[i][j]=Max(dp[i][j],D.front().x+j*w[i].p);
            if(j<w[i].s){
                while(D.size()&&dp[i-1][j]-j*w[i].p>=D.back().x)D.pop_back();
                D.push_back((pi){dp[i-1][j]-j*w[i].p,j});
            }
        }
    }printf("%d",dp[k][n]);
    return 0;
}
template<class free>
il free Max(free a,free b){
    return a>b?a:b;
}
il void read(int &x){
    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}

Fence

原文：https://www.cnblogs.com/a1b3c7d9/p/10961964.html