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