单调队列优化DP

注意这道题不再是滑动窗口了，而是左端点可不断变化，右端点不变的收缩窗口维护区间最值
亦可以用单调队列维护
本题细节较多，方程式推导写在代码中

#include<bits/stdc++.h>
using namespace std;
const int N = 16005,M = 105;
typedef long long LL;
#define pb push_back
#define F(i,a,b) for(int i=a;i<=b;i++)
#define dF(i,b,a) for(int i = b;i>=a;i--)
struct node
{
    int l,p,s;
} a[N];
bool cmp(node a,node b){ return a.s < b.s;}
int n,m,q[N],f[M][N];
/*
    f[i][j]:前i个工匠刷前j个木板（可以不刷）的最大报酬
    f[i][j] = max(f[i-1][j],f[i][j-1],f[i-1][k]+(j-k)*p[i])
    k+1<=s[i]<=j && j-k<=l[i]
    分离方程式得到：f[i][j] = max{f[i-1][k]-k*p[i]}+j*p[i] ( j-l[i] <= k <= s[i]-1 )
*/
int calc(int i,int k){ return f[i-1][k]-k*a[i].p;}
int main()
{
    cin>>n>>m;
    F(i,1,m) cin>>a[i].l>>a[i].p>>a[i].s;
    sort(a+1,a+m+1,cmp);
    F(i,1,m)
    {
        int st = 1,ed = 0;
        F(k,max(0,a[i].s-a[i].l),a[i].s-1)
        {
            while(st <= ed && calc(i,q[ed]) <= calc(i,k)) ed--;
            q[++ed] = k;
        }
        F(j,1,n)
        {
            f[i][j] = max(f[i-1][j],f[i][j-1]);
            if(j >= a[i].s)
            {
                while(st <= ed && q[st] < j-a[i].l) st++;
                if(st <= ed) f[i][j] = max(f[i][j],calc(i,q[st])+j*a[i].p);
            }
        }
    }
    cout << f[m][n] << '\n';
    return 0;
}