P2569 [SCOI2010]股票交易
题目大意：
冷笑话购物网预知了 \(T\) 天的股票走势，已知第 \(i\) 天购入价为每股 \(AP_i\) ,卖出价为每股 \(BP_i\)
（数据保证对于\(\forall i\)，都有 \(AP_i \geq BP_i\)
），一次买入至多只能购买 \(AS_i\)股，一次卖出至多只能卖出 \(BS_i\)股。两次交易要间隔 \(W\) 天，且手中的股票不能超过 \(MP\) 股。求赚的最多的钱。
solution:
能感觉到是一道 \(\text{DP}\) 题。我们来设个状态 \(f_{i,j}\) 表示第 \(i\) 天，手中有 \(j\) 股股票的最大收益。
分一下几种情况讨论：
- 第 \(i\) 天什么也不干：
- 第 \(i\) 天从 \(0\) 支购进：
- 第 \(i\) 天买进：
- 第 \(i\) 天卖出：
直接枚举 \(k\) 的话复杂度爆炸，所以我们推一下柿子（以买入为例）：
\[f_{i,j}=\max \{f_{i,j},f_{i-w-1,k}-(j-k)\times AP_i\} \]打开括号：
\[f_{i,j}=\max \{f_{i,j},f_{i-w-1,k}-j\times AP_i+k\times AP_i\} \]转化一下，先找出后面柿子的最大值，再和 \(f_{i,j}\) 取 \(\max\) 。
\[f_{i,j}= f_{i-w-1,k}-j\times AP_i+k\times AP_i \]移项：
\[f_{i,j}= f_{i-w-1,k}+k\times AP_i-j\times AP_i \]分成两段：
\[f_{i-w-1,k}+k\times AP_i \]与：
\[j\times AP_i \]前面那个只跟 \(k\) 有关，后面的是一个定值。就形如：
\[f_i=\max\{f_j+cal(i)\} \]那么我们把前面的那个柿子扔进单调队列，后面的那个实时算出。就降低了时间复杂度。
细节处理：
- 买入时要正序枚举，而卖出时要倒序枚举。因为后面的股票数比前面的大才能卖出。
- \(f\) 数组初始化极小值。
- 单调队列要初始化头尾。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2003;
int ap,bp,as,bs;
int f[N][N],q[N],hd,tl;
int main(){
memset(f,0x80,sizeof(f));
int t,mp,w; scanf("%d%d%d",&t,&mp,&w);
for(int i=1;i<=t;i++){
scanf("%d%d%d%d",&ap,&bp,&as,&bs);
for(int j=0;j<=as;j++)
f[i][j]=-j*ap;
for(int j=0;j<=mp;j++)
f[i][j]=max(f[i][j],f[i-1][j]);
if(i<=w) continue;
hd=1,tl=0;
for(int j=0;j<=mp;j++){
while(hd<=tl&&q[hd]<j-as) hd++;
while(hd<=tl&&f[i-w-1][q[tl]]+q[tl]*ap<=f[i-w-1][j]+j*ap)
tl--;
q[++tl]=j;
if(hd<=tl) f[i][j]=max(f[i][j],f[i-w-1][q[hd]]+q[hd]*ap-j*ap);
}
hd=1,tl=0;
for(int j=mp;j>=0;j--){
while(hd<=tl&&q[hd]>bs+j) hd++;
while(hd<=tl&&f[i-w-1][q[tl]]+q[tl]*bp<=f[i-w-1][j]+j*bp)
tl--;
q[++tl]=j;
if(hd<=tl) f[i][j]=max(f[i][j],f[i-w-1][q[hd]]+q[hd]*bp-j*bp);
}
}
int ans=0;
for(int i=0;i<=mp;i++)
ans=max(ans,f[t][i]);
printf("%d",ans);
return 0;
}
最后附上丑陋手迹