欢迎各位观看我写的题解！如果觉得我写的对你有帮助的话可以点个赞！
题目样例:
Input:
8 4
3 2 2
3 2 3
3 3 5
1 1 7
Output:
17
分析题目后我们得知：本题可以运用动态规划解决
状态定义:f[i][j]表示前i个工人粉刷前j块木板之后得到的最大报酬
状态转移方程:
1.根据题意得知，第i个工人可以什么也不做，所以转移方程的第一种情况:f[i][j]=f[i-1][j];
2.同时，第i个工人完全可以不刷第j块木板，所以转移方程的第二种情况:f[i][j]=f[i][j-1];
3.第3种情况说明的是：如果工人i粉刷k+1~j的木板，则转移方程的第三种情况出现：f[i][j]=f[i-1][k]+p[i]*(j-k)
对于第3种情况，可能同学们不能很快理解，那么作者就详细说明一下：（dalao可以跳过）
1.如果工人i粉刷区间[k+1,j]内的木板，则j-(k+1)+1(这是指区间的长度)<=Li,化简后得:j-k<=Li
2.题目规定这个工人至多粉刷Li个板子,且他必须粉刷第Si个板子,所以我们得知:k+1<=Si<=j
如果同学们还是不太理解的话就可以收藏起来反复思考哦！
好了，我们可以写代码了！
但是到了这一步，我们发现，如果就这样去DP，你的测评记录可能出现这个：
我们可以仔细观察一下我们的转移方程：真正决定方程的只有状态变量j和决策变量k
同学们可能会联想到我们的单调队列
没错，这题是可以用单调队列进行优化的，具体可以康康代码：
//题解仅供同学们参考，请勿抄袭哦，谢谢！
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=16100,M=150;
struct Each_node
{
int l;
int p;
int s;
};
Each_node a[N];
int n,m,f[M][N],hh,tt=-1,q[N];
bool cmp(const Each_node &x,const Each_node &y)
{
return x.s<y.s;
}//为啥要按S排序呢？
int calc(int num,int k)
{
return f[num-1][k]-a[num].p*k;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d %d %d",&a[i].l,&a[i].p,&a[i].s);
//显然的DP题，但是这里逐个枚举k非常的麻烦，耗时也多，所以可以用单调队列进行优化
//问题来了，怎么优化呢？
//我也不知道
//假的
//我们可以维护一个单调递减序列，这样在队首的元素将会是最大的
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
{
hh=0,tt=-1;
for(int k=max(0,a[i].s-a[i].l);k<=a[i].s-1;k++) //k从max(0,a[i].s-a[i].l)开始的原因是因为a[i].s-a[i].l可能小于0
{
while(hh<=tt && calc(i,q[tt])<=calc(i,k))
tt--; //单调递减队列
q[++tt]=k; //元素k入队
}
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
//粉刷第 k+1~j块模木板时的转移
if(j>=a[i].s)
{
//排除队头不合法的决策
while(hh<=tt && q[hh]<j-a[i].l)
hh++;
//队列非空时，取队头进行状态转移
if(hh<=tt)
f[i][j]=max(f[i][j],calc(i,q[hh])+a[i].p*j);
}
}
}
printf("%d",f[m][n]);
return 0;
}
