倍增DP太难啦心情好再回去做
poj1821 先让工匠按s排序，f[i][j]表示枚举到第i个工匠涂了j个木板（注意第j个木板不一定要涂）
那么f[i][j]可以直接继承f[i-1][j]和f[i][j-1]
此外 f[i][j]=max(j-l[i]+1<=k<=s[i]){f[i-1][k-1]+(j-k+1)*p}
按照单调队列运用的思想，维护f[i-1][k-1]-k*p的最大值
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node{int l,p,s;}a[110]; bool cmp(node n1,node n2){return n1.s<n2.s;} int f[110][21000]; int h,t,q[21000]; int main() { int m,n; scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s); sort(a+1,a+n+1,cmp); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { h=1,t=0; for(int k=max(1,a[i].s-a[i].l+1);k<=a[i].s;k++) { while(h<=t&&f[i-1][k-1]-a[i].p*k>=f[i-1][q[t]-1]-a[i].p*q[t])t--; q[++t]=k; } for(int j=1;j<a[i].s;j++)f[i][j]=max(f[i-1][j],f[i][j-1]); for(int j=a[i].s;j<=m;j++) { while(h<=t&&max(1,j-a[i].l+1)>q[h])h++; f[i][j]=max(f[i-1][j],f[i][j-1]); if(h<=t)f[i][j]=max(f[i][j],a[i].p*(j+1)+f[i-1][q[h]-1]-a[i].p*q[h]); } } printf("%d ",f[n][m]); return 0; }
poj3017 神题（其实还好吧）
设f[i]表示1~i的最小值，f[i]=min(∑(k=j+1~i)a[k]<=m){f[j]+max(j+1~i)(a[k])}
然而，可以证明的是，可能成为最优决策的j，一定是j+1~i的最大值，或者是满足∑(k=j+1~i)a[k]<=m最小的j
那么就可以维护一个a[j]递减的单调队列，但是f[j]+max(j+1~i)(a[k])是不单调的，要用set把值记录
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> using namespace std; typedef long long LL; int a[110000],q[110000]; LL f[110000]; multiset<LL>s; int main() { int n;LL m; scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]>m){printf("-1 ");return 0;} } int tp=1;LL sum=0; int h=1,t=0; for(int i=1;i<=n;i++) { sum+=a[i];while(sum>m)sum-=a[tp++]; while(h<=t&&a[i]>=a[q[t]]) { if(h<t)s.erase(f[q[t-1]]+a[q[t]]); t--; } q[++t]=i; if(h<t)s.insert(f[q[t-1]]+a[q[t]]); while(h<=t&&tp>q[h]) { if(h<t)s.erase(f[q[h]]+a[q[h+1]]); h++; } f[i]=f[tp-1]+a[q[h]]; if(h<t)f[i]=min(f[i],*s.begin()); } printf("%lld ",f[n]); return 0; }
hdu2191 （纯粹是给单调队列维护多重背包找个例题）
把一个数拆成u+p*V的形式，f[u+p*V]=max(p-C<=k<=p-1){f[u+k*V]+(p-k)*W}
维护下f[u+k*V]-k*W
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int f[110],q[110]; int main() { int T; scanf("%d",&T); while(T--) { int m,n,W,V,C; scanf("%d%d",&m,&n); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { scanf("%d%d%d",&V,&W,&C); for(int u=0;u<V;u++) { int h=1,t=0; int li=(m-u)/V; for(int k=max(0,li-C);k<=li-1;k++) { while(h<=t&&(f[u+q[t]*V]-q[t]*W)<=(f[u+k*V]-k*W))t--; q[++t]=k; } for(int p=li;p>=0;p--) { while(h<=t&&q[h]>p-1)h++; if(h<=t)f[u+p*V]=max(f[u+p*V],f[u+q[h]*V]+(p-q[h])*W); if(p-C-1>=0) { while(h<=t&&(f[u+q[t]*V]-q[t]*W)<=(f[u+(p-C-1)*V]-(p-C-1)*W))t--; q[++t]=p-C-1; } } } } int ans=0; for(int i=1;i<=m;i++)ans=max(ans,f[i]); printf("%d ",ans); } return 0; }