此题链接到dp常见优化方法
开始的时候被纪念品误导，以为是多支股票，后来发现事情不妙：
这道题知道的是某一只股票的走势；
(Solution):
(70pts):
设(f[i][j])表示第i天持有j股股票可以获得的最大利润，有如下转移方程：
(f[i][j]=Maxegin{cases}f[i-1][j] //第i天不买也不卖 \-Ap[i]*j // 第i天之前不持有股票，第i天买入j股股票 \f[i-w-1][k]-Ap[i]*(j-k) Max(0,j-As[i])leq k< j //第i天买入j-k股股票 \f[i-w-1][k]+Bp[i]*(k-j) j<kleq Min(MaxP,j+Bs[i]); //第i天卖出k-j股股票 end{cases})
为什么转移是第(i-w-1)天而不是第(i-w-2)亦或其它日子呢？
借用一段话(原文：
看第一种情况（第i天不买也不卖），我们已经把某一天以前的最优答案转移到了该天，所以从那一天转移，相当于从那一天包括前面任何一天开始转移，省去了大把时间。
利用上面的四个式子就可以写出代码,注意初始化的时候要将(f[ ][ ])初始化为一个很小的负数，(f[0][0]=0)
(Code：)
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}const int mxt=5010;
int T,MaxP,w;
int Ap[mxt],Bp[mxt],As[mxt],Bs[mxt];
int f[mxt][mxt];
int main() {
T=read();
MaxP=read();
w=read();
for(int i=1;i<=T;i++) {
Ap[i]=read();
Bp[i]=read();
As[i]=read();
Bs[i]=read();
}
memset(f,0x9f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=T;i++) {
for(int j=0;j<=MaxP;j++) {
f[i][j]=f[i-1][j];
if(i-w-1>=0) {
for(int k=max(0,j-As[i]);k<j;k++)
f[i][j]=max(f[i][j],f[i-w-1][k]-Ap[i]*(j-k));
for(int k=j+1;k<=min(MaxP,j+Bs[i]);k++) {
f[i][j]=max(f[i][j],f[i-w-1][k]+Bp[i]*(k-j));
}
}
if(j<=As[i])
f[i][j]=max(f[i][j],-Ap[i]*j);
printf("%d ",f[i][j]);
}
puts("");
}
printf("%d",f[T][0]);
return 0;
}
但不要以为这样就可以愉快的(mathfrak{AC})这道题，它毕竟是一道省选题(color{white}{（虽然年代已经很久远了})
实际复杂度(O(T*MaxP^2))，在(T)和(MaxP)都是(2000)的数量级的数据下，显然是过不去的（不要妄想跑过(8e9)
因此我们需要优化
看数据范围(2000)大致可以猜测是一个(O(n^2))的代码
观察第(3、4)个式子，暴力拆解得到：
(f[i][j]=Max{f[i-w-1][k]-Ap[i]*j+Ap[i]*k})
(f[i][j]=Max{f[i-w-1][k]-Bp[i]*j+Bp[i]*k})
显然(-Bp[i]*j)与(-Ap[i]*j)的值不影响我们取最大值，因此我们可以提出来：
(f[i][j]=Max{f[i-w-1][k]+Ap[i]*k}-Ap[i]*j)
(f[i][j]=Max{f[i-w-1][k]+Bp[i]*k}-Bp[i]*j)
这两个式子像什么？像极了单调队列优化！
所以采用单调队列优化我们的第(3、4)个式子，就可以做到(O(n^2))完成这道题（胜利的曙光(color{GOld}{！！！})
h=1;t=0;
for(int j=0;j<=MaxP;j++) {//购买股票，从小往大更新
while(h<=t&&q[h]<j-As[i])
//清除队首中不符合"第i天的一次买入至多只能购买AS_i股"的
h++;
while(h<=t&&cost1(i,q[t])<=cost1(i,j))
//如果队尾的收入<=当前的收入，弹出队尾（从前往后更新，i要大于q[t]，如果队尾的收入<=当前的收入，显然i相比于q[t]一定更优）
t--;
q[++t]=j;
if(h<=t) //队列中有元素
f[i][j]=max(f[i][j],cost1(i,q[h])-Ap[i]*j);
}
h=1;t=0;
for(int j=MaxP;j>=0;j--) {//卖出股票，从大往小更新：由4式知，j位置的状态是从一个>j的位置转移而来的，因此倒序更新
while(h<=t&&q[h]>j+Bs[i])
h++;
while(h<=t&&cost2(i,q[t])<=cost2(i,j))
t--;
q[++t]=j;
if(h<=t)
f[i][j]=max(f[i][j],cost2(i,q[h])-Bp[i]*j);
}
(Code:)
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}const int mxt=5010;
int T,MaxP,w;
int Ap[mxt],Bp[mxt],As[mxt],Bs[mxt];
int f[mxt][mxt];
int q[mxt];
int h,t;
int cost1(int i,int j) {
return f[i-w-1][j]+Ap[i]*j;
}
int cost2(int i,int j) {
return f[i-w-1][j]+Bp[i]*j;
}
int main() {
T=read();
MaxP=read();
w=read();
for(int i=1;i<=T;i++) {
Ap[i]=read();
Bp[i]=read();
As[i]=read();
Bs[i]=read();
}
memset(f,0x9f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=T;i++) {
for(int j=0;j<=MaxP;j++) {
f[i][j]=f[i-1][j];
if(j<=As[i])
f[i][j]=max(f[i][j],-Ap[i]*j);
}
if(i-w<=0) continue;
h=1;t=0;
for(int j=0;j<=MaxP;j++) {
while(h<=t&&q[h]<j-As[i]) h++;
while(h<=t&&cost1(i,q[t])<=cost1(i,j)) t--;
q[++t]=j;
if(h<=t)
f[i][j]=max(f[i][j],cost1(i,q[h])-Ap[i]*j);
}
h=1;t=0;
for(int j=MaxP;j>=0;j--) {
while(h<=t&&q[h]>j+Bs[i]) h++;
while(h<=t&&cost2(i,q[t])<=cost2(i,j)) t--;
q[++t]=j;
if(h<=t)
f[i][j]=max(f[i][j],cost2(i,q[h])-Bp[i]*j);
}
}
printf("%d",f[T][0]);
return 0;
}