记录编号	573149	评测结果	AAAAAAAAAA
题目名称	[POJ 1821]粉刷栅栏	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2022-07-19 12:44:55	内存使用	3.81 MiB

/*
f(i,j): 安排前 i 个工匠粉刷前 j 块木板(可以有空着不刷的),工匠们能获得的最大报酬;
(1)第 i 个工匠可以什么也不刷,此时：f(i,j) = f(i-1,j);
(2)第 j 块木板可以 空着 不刷,此时：f(i,j) = f(i,j-1);
(3)第 i 个工匠粉刷 [k+1,j] 的木板，总数不超过Li且必须包含Si，
故：k+1<=Si<=j  =>  k<=Si-1;  j-k<=Li  =>  k>=j-Li
f(i,j)=max{ f(i-1,k)+Pi*(j-k) } (j-Li<=k<=Si-1, j>=Si)

优化：（细节请参考《算法竞赛进阶指南》 P315）
考虑内层循环j以及决策k时,可以把外层i看作定值,状态转移方程可改为：
f(i,j)=Pi*j + max{ f(i-1,k)-Pi*k } (j-Li<=k<=Si-1, j>=Si)
当j增大时,决策 k 的取值范围上界Si-1不变，下界j-Li变大，按与“最大子序列和”一题
类似的想法，我们比较任意2个决策k1和k2，不妨假设k1<k2<=Si-1：
因为k2>k1，随着j增大，k1会比k2更早从范围[j-Li,Si-1]中被排除，如果还满足:
 f(i-1,k1)-pi*k1<=f(i-1,k2)-pi*k2,那么就意味着k2比k1更优且存活期更长。
 这种情况下,k1就是无用决策，从候选集排除即可。
 综上所述，可以维护一个决策点k单调递增，数值f(i-1,k)-pi*k单调递减的队列。
 只有队列中的决策才有可能在某一时刻成为最优决策。
 该单调队列支持如下操作：
 1、j变大时，检查队头，把小于j-Li的决策出队；
 2、需要查询最优决策时，队头即所求；
 3、新决策需要加入候选集时，在队尾检查f(i-1,k)-pi*k的单调性，把无用决策出队，最后新决策入队。
 具体操作：
 内循环开始时(j=Si)，建立空队列，把[max(Si-Li,0) , Si-1]中的决策加入候选集(操作3).对于每个j=Si~N,
 检查决策合法性(操作1),然后取队头为最优决策(操作2)进行状态转移。
 
 每个决策最多入队、出队1次，故转移时间复杂度均摊O(1),整体时间复杂度O(NM)
*/
#include <bits/stdc++.h>
using namespace std;

const int N=16010,M=110;
struct rec{ int L,P,S; }a[N];//木板
int n,m,f[M][N],q[N];

bool operator <(rec a,rec b)
{
	return a.S<b.S;
}

int calc(int i,int k)
{
	return f[i-1][k]-a[i].P*k;
}


int main()
{
	freopen("fence_paint.in","r",stdin);
	freopen("fence_paint.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>a[i].L>>a[i].P>>a[i].S;
	sort(a+1,a+m+1);//Si从小到大排序
	for(int i=1;i<=m;i++)
	{	
		int l=1,r=0;//初始化单调队列
		
		for(int k=max(0,a[i].S-a[i].L);k<=a[i].S-1;k++)
		{//把最初的候选集入队
			//插入新决策，维护队尾单调性
			while(l<=r && calc(i,q[r]) <= calc(i,k))
				r--;//无用决策出队
			q[++r]=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(l<=r && q[l]<j-a[i].L)l++;
				//队列非空时，取队头作为最优策略进行状态转移
				if(l<=r)
					f[i][j]=max(f[i][j],calc(i,q[l])+a[i].P*j);
			}//if
		}//for j
	}//for i
	cout<<f[m][n]<<endl;
	return 0;
}