poj1821

题目链接
大意：给你n个木块，k个人。每个人有三个参数 $l,p,s$l,p,s,分别表示每个人最多加工的木块数，每个人加工一个木块的贡献，每个人加工木块区间必须包含的 木块编号
思路：先看题，考虑 $dp\left[i\right]\left[j\right]$dp[i][j]表示第i个人加工到j号木块的最大贡献， $T\left[i\right]$T[i]表示加工i个木块的最大贡献
然后我们每次遍历i转移就是
$dp\left[i\right]\left[j\right]=max\left(T\right[x]+(j-x)\ast p[i\left].p\right),x\in \left[p\right[i].s-l,p[i\left].s\right)。j\in \left[p\right[i].s,p[i].s+p[i].l-1)$dp[i][j]=max(T[x]+(j−x)∗p[i].p),x∈[p[i].s−l,p[i].s)。j∈[p[i].s,p[i].s+p[i].l−1)
$T\left[k\right]=max\left(T\right[k],dp[i\left]\right[k\left]\right),k\in [0,n]$T[k]=max(T[k],dp[i][k]),k∈[0,n]
然后我们发现转移是选 $T\left[x\right]-x\ast p\left[i\right].p$T[x]−x∗p[i].p最大的进行转移，然后我们可以维护一个递减的单调队列，放当前的值，和位置下标。
转移的时候弹出不合法的元素，然后直接取队头的进行转移即可，时间复杂度 $O\left(nk\right).$O(nk).

#include<iostream>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <stdlib.h>
#include <string.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int n,k;
struct uzi
{
	LL l,p,s;
}p[N];
int cmp(uzi x,uzi y){
	return x.s<y.s;
}
LL f[111][16123],T[16123];
pair<LL,int>Q[N];
int l,r;
int main(){
	while(cin>>n>>k){
		for(int i=1;i<=k;i++)cin>>p[i].l>>p[i].p>>p[i].s;
		LL ans=0;
		sort(p+1,p+1+k,cmp);
		for(int i=1;i<=k;i++){
			l=0,r=0;
			Q[0].se=-1e9;
			for(int j=p[i-1].s;j<=p[i-1].s+p[i-1].l-1&&j<=n;j++)T[j]=max(T[j],f[i-1][j]);
			for(int j=max(0ll,p[i].s-p[i].l);j<p[i].s;j++){
				LL tmp=T[j]-j*p[i].p;
				while(l<r&&tmp>=Q[r].fi)r--;
				pair<LL,int>na;
				na.fi=tmp;
				na.se=j;
				Q[++r]=na;
			}
			for(int j=p[i].s;j<=p[i].s+p[i].l-1&&j<=n;j++){
				while((l<r&&Q[l].se<j-p[i].l))l++;
				f[i][j]=max(Q[l].fi+j*p[i].p,f[i][j]);
				ans=max(ans,f[i][j]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}