题解 P2569 【[SCOI2010]股票交易】

zyzzyzzyzzyz

2018-12-18 19:50:06

Solution

也可以在[我的博客](https://www.cnblogs.com/Zenyz/p/10139276.html)食用,效果更佳 ---- 第一道单调队列优化DP,写篇题解纪念一下 [P2569 [SCOI2010]股票交易](https://www.luogu.org/problemnew/show/P2569) 题面很简单,我用$n,m,buy,sell,blimit,slimit$来分别代表$T,MaxP,AP,BP,AS,BS$ ## 1.暴力 ​ 应该挺好打的,转移如下 ​ $f[i][j]=max(f[i-1][j],f[i][j])$ ​ $f[i][j]=MAX_{k=0}^{j}(f[i-w-1][k]-buy[i]\times(j-k)),((j-k)<blimit[i])$ ​ $f[i][j]=MAX_{k=j}^{j+sli}(f[i-w-1][k]+sell[i]\times(k-j)),((k-j)<slimit[i])$ ​ $(MAX$表示区间最大$)$ ​ 这样做是$O(n^2)$的,TLE ## 2.单调队列优化DP ​ 考虑优化, ​ 每次转移如下(以买入为例): ​ $f[i][j]=f[i-w-1][k]-buy[i]\times(j-k)),((j-k)<blimit[i])$ ​ $RHS=f[i-w-1][k]-buy[i]*j+buy[i]*k,((j-k)<blimit[i]) $ ​ 那么我们到底有没有必要枚举$k$ 呢? ​ 在枚举$k$ 的过程中,$-buy[i]*j$ 是定值,我们把它放到一边 ​ 令数组$a[k]=f[i-w-1][k]+buy[i]*k$ ​ 那么$a$ 是一个与$i,j$ 无关的数组, ​ 且$f[i-w-1][j]$的答案只会从$a$ 数组中产生 ​ 则转移的本质其实是从同层且满足限制条件(条件即为blimit)的答案中选取最大的进行转移 ​ ![]( https://cdn.luogu.com.cn/upload/pic/46564.png ) ​ 如上图每次只会增加一个元素,减去一个元素 ​ 然后就[滑动窗口](https://www.luogu.org/problemnew/show/P1886)了 ## 3.代码 暴力(50pts): ```cpp #include<bits/stdc++.h> #define il inline #define R register int #define ll long long #define gc getchar using namespace std; il int rd() { R x=0,flag=1; char ch=0; while((ch>'9'||ch<'0')&&ch!='-')ch=gc(); if(ch=='-')flag=-1,ch=gc(); while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=gc(); return x*flag; } const int N=2010; int n,m,w,ans; int f[2002][2002]; int buy[N],sell[N],slimit[N],blimit[N]; int main () { n=rd(),m=rd(),w=rd(); for(R i=1;i<=n;i++) buy[i]=rd(),sell[i]=rd(),blimit[i]=rd(),slimit[i]=rd(); memset(f,0xcf,sizeof(f)); for(R i=1;i<=n;i++) for(R j=0;j<=blimit[i];j++) f[i][j]=-buy[i]*j; for(R i=1;i<=n;i++) { for(R j=0;j<=m;j++) { f[i][j]=max(f[i][j],f[i-1][j]); for(R k=0;k<=slimit[i];k++) { if(i>w) f[i][j]=max(f[i][j],f[i-w-1][j+k]+sell[i]*k); } for(R k=0;k<=blimit[i];k++) { if(i>w&&j>=k) f[i][j]=max(f[i][j],f[i-w-1][j-k]-buy[i]*k); } } } for(R i=0;i<=m;i++) ans=max(ans,f[n][i]); cout<<ans<<endl; return 0; } ``` 正解(100pts,跑得巨慢): ```cpp #include<bits/stdc++.h> #define il inline #define R register int #define ll long long #define gc getchar using namespace std; il int rd() { R x=0,flag=1; char ch=0; while((ch>'9'||ch<'0')&&ch!='-')ch=gc(); if(ch=='-')flag=-1,ch=gc(); while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=gc(); return x*flag; } const int N=2010; int n,m,w,ans; int f[2002][2002]; int buy[N],sell[N],slimit[N],blimit[N]; deque<int> dq,dq2; int main () { n=rd(),m=rd(),w=rd(); for(R i=1;i<=n;i++) buy[i]=rd(),sell[i]=rd(),blimit[i]=rd(),slimit[i]=rd(); memset(f,0xcf,sizeof(f));f[0][0]=0; for(R i=1;i<=n;i++) { while (!dq.empty()) dq.pop_back(); while (!dq2.empty()) dq2.pop_back(); R t=max(0,i-w-1); for(R j=0;j<=m;j++) { f[i][j]=max(f[i][j],f[i-1][j]); while(dq.size()&&f[t][j]>=f[t][dq.back()]-buy[i]*(j-dq.back())) dq.pop_back(); dq.push_back(j); while(dq.size()&&j-dq.front()>blimit[i])dq.pop_front(); f[i][j]=max(f[i][j],f[t][dq.front()]-buy[i]*(j-dq.front())); } for(R j=m;j+1;j--) { while(dq2.size()&&f[t][j]>=f[t][dq2.back()]+sell[i]*(dq2.back()-j)) dq2.pop_back(); dq2.push_back(j); while(dq2.size()&&dq2.front()-j>slimit[i])dq2.pop_front(); f[i][j]=max(f[i][j],f[t][dq2.front()]+sell[i]*(dq2.front()-j)); } } for(R i=0;i<=m;i++) ans=max(ans,f[n][i]); cout<<ans<<endl; return 0; } ``` ​