有一个长度为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();
}