P2569 [SCOI2010]股票交易 题解
Post time: 2020-07-28 11:35:02
传送门
题意简述：
lxhgww 要通过买卖股票来赚最大的钱。他预测了 \(T\) 天的股票走势，每一天都有一个买入价 \(AP_i\) 和一个卖出价 \(BP_i\)（还有一个奇怪的限制 \(AP_i\geq BP_i\)）。每天都有一个购买股票的上限和卖出股票的上限，分别为 \(AS_i\) 和 \(BS_i\)。还有两个大限制是：lxhgww 手中最多有 \(MaxP\) 股，并且如果第 \(i\) 天发生交易（买入或卖出），那么他第 \(i+1\) 到 \(i+w\) 天都不能交易。
题解：
题目条件很复杂，我们不要被它吓到，一点一点分析，最终积少成多就能轻松 AC 此题！
显然这应该是一道 DP。我们首先考虑 dp 数组的意义：为了满足无后效性，我们需要将题目中有关的条件都设置到 dp 数组的状态中。
于是我们得到：用 \(f_{i,j}\) 表示第 \(i\) 天，那个人手里有 \(j\) 支股票的最大利润（注意！因为一开始要买，所以可能为负数，一开始要赋成负无穷）。最终的结果就是在第 \(n\) 天手里的股票数为 \(0\sim MaxP\)的最大利润（即 \(\max_{j=0,j<=MaxP}f_{n,j}\)）。
接下来我们的状态转移就需要分情况各个击破了。对于 \(f_{i,j}\) 来说，可以有这样 4 种转移：
-
在第 \(i\) 天一气买 \(j\) 个，即 \(f_{i,j}=\max(f_{i,j},-AP_i* j) (0\leq j\leq AS_i)\)
-
第 \(i\) 天什么也不干，即 \(f_{i,j}=\max(f_{i,j},f_{i-1,j}) (0\leq j\leq MaxP)\)
-
第 \(i\) 天买 \(k\) 只股票。因为每次交易要隔 \(w\) 天，所以最近一次的交易最晚要在第 \(i-w-1\) 天。又因为第 2 步，我们已经统计了每一天什么也不干的情况，所以 \(f_{i-w-1,j}\) 应当是在 \(1\) 到 \(i-w-1\) 天里交易的最大利润。即：\(f_{i,j}=max(f_{i,j},f_{i-w-1,k}-(j-k)\cdot AP_i)(j-AS_i\leq k
-
第 \(i\) 天卖股票。同上，我们仍然要限制最晚要在 \(i-w-1\) 天交易。即：\(f_{i,j}=\max(f_{i,j},f_{i-w-1,k}+(k-j)\cdot BP_i)(j
上面的 (1)(2) 很好维护，我们将 (3)(4) 两式拆括号，可以得到：
\[\begin{aligned} f_{i,j}&=\max(f_{i-w-1,k}+k\cdot AP_i)-j\cdot AP_i(j-AS_i\leq k很明显满足单调队列优化的要求：\(\max/\min\)中只含一次项（关于 \(k\)），对于我们枚举的每一个 \(i\),当 \(i>w\) 时，我们可以用一个单调队列记录 \(f_{i-w-1,k}+k\cdot AP_i\) 的最大值递减序列，从而让时间复杂度由 \(O(n^3)\) 降至 \(O(n^2)\)。
这样我们将一道复杂的问题拆成了四个小问题，并逐一分析得到解决办法之后，这道题就完成啦！
几个注意事项：
- 要注意什么时候可以用单调队列优化，什么时候不能用。
- 要明确单调队列里边记录的是下标！下标！！下标！！！
- 对于每个 \(i\)，单调队列入队出队都可能不止一次，所以一定不要写成
if！要用while！ - 统计答案的时候，不要想当然，尽量涉及全面，有些题最后
f[n][m]（意会）不一定是这道题的最优解。 - 数组下标越界是个很恶心的错误，要注意只要调用数组，就先判越界。
最后放上非常丑的代码
点击查看代码
#include
#include
#include
using namespace std;
const int N=5000+4,INF=0x3f3f3f3f;
struct Queue{//使用手写队列来实现，我写了一个结构体，这样队列功能清晰一些
int qt[N],head,tail;
inline void clear(){head=1,tail=0;}
Queue(){clear();}
inline void pop_front(){++head;}
inline void pop_back(){--tail;}
inline void push(int x){qt[++tail]=x;}
inline int front(){return qt[head];}
inline int back(){return qt[tail];}
inline bool empty(){return head>tail;}
}q;
int n,m,w,ap,bp,as,bs;
int f[N][N];
int main(){
memset(f,0xcf,sizeof(f));//不要忘了初始化成负无穷
scanf("%d%d%d",&n,&m,&w);
for(int i=1;i<=n;++i){
scanf("%d%d%d%d",&ap,&bp,&as,&bs);//完全可以边读入边做，省一点空间
for(int j=0;j<=as;++j) f[i][j]=-ap*j;//第一种子情况
for(int j=0;j<=m;++j) f[i][j]=max(f[i][j],f[i-1][j]);//第二种子情况
if(i<=w) continue;//后面要用i-w-1，数组不能越界
q.clear();//使用之前清空队列是个好习惯
for(int j=0;j<=m;++j){//第三种情况
while(!q.empty()&&j-q.front()>as) q.pop_front();
while(!q.empty()&&f[i-w-1][q.back()]+q.back()*ap<=f[i-w-1][j]+j*ap) q.pop_back();
q.push(j);
if(!q.empty()) f[i][j]=max(f[i][j],f[i-w-1][q.front()]+q.front()*ap-j*ap);
}
q.clear();
for(int j=m;j>=0;--j){//第四种情况
while(!q.empty()&&q.front()-j>bs) q.pop_front();
while(!q.empty()&&f[i-w-1][q.back()]+q.back()*bp<=f[i-w-1][j]+j*bp) q.pop_back();
q.push(j);
if(!q.empty()) f[i][j]=max(f[i][j],f[i-w-1][q.front()]+q.front()*bp-j*bp);
}
}
int ans=0;
for(int i=0;i<=m;++i) ans=max(ans,f[n][i]);
printf("%d\n",ans);//最终要卖完所有股票所以输出
return 0;
}