考虑把工人按照 $s_i$ 排序，那么设 $f_{i,j}$ 表示前 $i$ 个工人粉刷前 $j$ 个栅栏的最大收益。

那么有转移方程：

$f_{i,j}=\max\limits_{k=\max(0,j-l_i)}^{s_i} f_{i-1,k}+p_i\times(j-k)$

考虑把 $p_i\times j$ 的贡献提出来，那么就有：

$f_{i,j}=p_i\times j+\max\limits_{k=\max(0,j-l_i)}^{s_i-1} f_{i-1,k}-p_i\times k$

注意围墙和工人都不是必须要刷。

也就是还有：

$f_{i,j}\gets \max(f_{i,j},f_{i-1,j},f_{i,j-1})$

不想写单调队列，直接用线段树维护最大值做就完了。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e4+5,M=105;
struct SEGMENT{
    int s[N<<2];
    void build(int k,int l,int r,int val,int a[]){
        if(l==r){
            s[k]=a[l]-val*l;
            return ;
        }
        int mid=(l+r)/2;
        build(k*2,l,mid,val,a);
        build(k*2+1,mid+1,r,val,a);
        s[k]=max(s[k*2],s[k*2+1]);
    }
    int ask(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y){
            return s[k];
        }
        if(y<l||r<x){
            return -1e9+7;
        }
        int mid=(l+r)/2;
        return max(ask(k*2,l,mid,x,y),ask(k*2+1,mid+1,r,x,y));
    }
}tree;
struct node{int l,p,s;}a[N];
int n,m;
int f[M][N];
bool cmp(node a,node b){return a.s<b.s;}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].p>>a[i].s;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        tree.build(1,0,m,a[i].p,f[i-1]);
        for(int j=1;j<=m;j++){
			f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(j>=a[i].s){
                f[i][j]=max(f[i][j],a[i].p*j+tree.ask(1,0,m,j-a[i].l,a[i].s-1));
            }
        }
    }
    cout<<f[n][m]<<'\n';
    return 0;
}

不知道为什么 POJ 上过不了。