注意：这题题意是有操作的天数相隔要大于w
然后列出状态转移方程就可以发现，可以用优点队列优化啦。
构造状态dp[i][j]表示第i 天拥有 j只股票的时候，赚了多少钱
状态转移有：
1、从前一天不买不卖:
dp[i][j]=max(dp[i-1][j],dp[i][j])
2、从前i-W-1天买进一些股:
dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])
3、从i-W-1天卖掉一些股:
dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])
// // main.cpp // hdu3401 // // Created by New_Life on 16/8/16. // Copyright © 2016年 chenhuan001. All rights reserved. // #include <iostream> #include <stdio.h> #include <algorithm> #include <queue> #include <string.h> #include <string> using namespace std; #define N 2020 #define INF 100000000 /******************_单调队列模板_******************/ //基于单调队列功能的单一性：以limit为序查找在一定范围内的极值。 //复杂度：O(n) //用法： 创建的时候调用.init() // 插入队列:.push( Q_Node( KEY,LIMIT ) ); // 设置limit值:.setlimit( LIMIT ); // 查询<limit值的最大元素: Q_Node qn; q2.top(qn); // 再查询前需要设置limit值，如果队列为空返回false,否则将最大元素存入qn中并返回true struct Q_Node { int key,limit;//用来比较大小的key和控制存在时间的limit Q_Node(){} Q_Node(int _key,int _limit){ key=_key,limit=_limit; } }; struct Q_Que { Q_Node Q[N]; int qf,qd; int limit;// <limit 的元素将被弹出 void init() { qf = qd = 0;//将队列内元素清空 } void push(Q_Node newnode) {//默认入队是当前limit最大的 while (qf>qd && Q[qf-1].key < newnode.key) qf--; Q[qf++] = newnode; } void setlimit(int _limit) { limit = _limit; } /* 取出队列中>=limit且key最大的元素。 */ bool top(Q_Node &rt) { while(qf>qd && Q[qd].limit < limit) qd++; if(qf==qd) return false; rt = Q[qd]; return true; } }q1,q2; int dp[N][N]; int ap[N],bp[N],as[N],bs[N]; int main(int argc, const char * argv[]) { int T; cin>>T; while(T--) { int t,mxp,w; cin>>t>>mxp>>w; for(int i=1;i<=t;i++) scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i); for(int i=0;i<=t;i++) for(int j=0;j<=mxp;j++) dp[i][j] = -INF; for(int i=1;i<=w+1;i++) for(int j=0;j<=as[i];j++) dp[i][j] = -j*ap[i]; dp[0][0] = 0; for(int i=1;i<=t;i++) { q1.init(); q2.init(); int sum1=0,sum2=0; for(int j=0;j<=mxp;j++) { dp[i][j] = max(dp[i][j],dp[i-1][j]);//啥也没做 } if(i <= w+1) continue; for(int j=0;j<=mxp;j++) { q1.push( Q_Node(dp[i-w-1][j]-sum1,j) ); q1.setlimit(j-as[i]); Q_Node qn; if(q1.top(qn)) { dp[i][j] = max(dp[i][j],qn.key+sum1); } sum1 -= ap[i]; } for(int j=mxp;j>=0;j--){ q2.push(Q_Node(dp[i-w-1][j]-sum2, -j)); q2.setlimit(-j-bs[i]); Q_Node qn; if(q2.top(qn)) dp[i][j] = max(dp[i][j],qn.key+sum2); sum2 += bp[i]; } } int ans = 0; for(int i=1;i<=t;i++) for(int j=0;j<=mxp;j++) ans= max(ans,dp[i][j]); cout<<ans<<endl; } return 0; } /* 20 5 2 0 2 1 1 1 2 1 1 1 3 2 1 1 4 3 1 1 5 4 1 1 5 3 0 2 1 2 2 2 1 12 1 3 2 2 1 4 3 3 2 5 4 1 2 5 2 3 2 1 3 2 1 1 12 1 3 2 2 2 4 3 3 3 5 4 1 2 5 3 3 2 1 3 2 1 1 12 1 3 4 2 2 1 3 3 3 1 3 3 5 5 10 0 2 1 3 2 1 1 12 1 3 4 2 2 1 3 3 3 1 3 3 5 5 10 0 2 1 3 2 1 1 12 0 3 4 4 2 1 3 0 3 1 3 0 5 4 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 3 1 1 10 4 3 1 3 1 1 1 5 1 1 1 10 6 1 1 10 6 1 1 */