题面传送门 这道题暴力dp是很好想的。 就是分别从上一天，最晚可转移的天，凭空买来转移。 因为有状态自然叠加所以只要转移最晚可转移的天就好了。 然后会发现这个是可以正反两边单调队列优化的。 复杂度 O ( T P ) O(TP) O(TP) 代码实现:
#include<cstdio> #include<cstring> #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; int n,m,w,x,y,z,f[2039][2039],q[2039],head,tail; int a[2039],b[2039],c[2039],d[2039]; int main(){ // freopen("1.in","r",stdin); register int i,j; scanf("%d%d%d",&n,&m,&w); for(i=1;i<=n;i++) scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); memset(f,-0x3f,sizeof(f)); for(i=1;i<=n;i++) f[i][0]=0; for(i=1;i<=n;i++){ for(j=1;j<=c[i];j++) f[i][j]=-a[i]*j; for(j=0;j<=m;j++) f[i][j]=max(f[i][j],f[i-1][j]); if(i<=w+1) continue; head=tail=0; for(j=0;j<=m;j++){ while(head!=tail&&q[head+1]+c[i]<j) head++; while(head!=tail&&f[i-w-1][q[tail]]-(j-q[tail])*a[i]<=f[i-w-1][j]) tail--; q[++tail]=j; f[i][j]=max(f[i][j],f[i-w-1][q[head+1]]-(j-q[head+1])*a[i]); } head=tail=0; for(j=m;j>=0;j--){ while(head!=tail&&q[head+1]>j+d[i]) head++; while(head!=tail&&f[i-w-1][q[tail]]+(q[tail]-j)*b[i]<=f[i-w-1][j]) tail--; q[++tail]=j; f[i][j]=max(f[i][j],f[i-w-1][q[head+1]]+(q[head+1]-j)*b[i]); } } printf("%d\n",f[n][0]); }