題目鏈接：戳我

看到這個題目，我們有一個樸素的DP想法（但是為什么我會先想到網(wǎng)絡(luò)流啊喂，果然是菜雞）

設(shè)\(dp[i][j][0/1/2]\)表示第i天不進行交易/買入/賣出，現(xiàn)在手上有j張票，前i天能夠獲得的最大收益。轉(zhuǎn)移什么的隨便弄弄就行了吧。

然后發(fā)現(xiàn)自己智障了，0/1/2根本不用劃分好嗎.......于是就變成了這個樣子......\(dp[i][j]\)表示現(xiàn)在手上有j張票，前i天能夠獲得的最大收益。

\(dp[i][j]=max(dp[i][j],dp[i-1][j])\)
\(dp[i][j]=max(dp[i][j],dp[i-w-1][k]-ap[i]*(j-k))\)
\(dp[i][j]=max(dp[i][j],dp[i-w-1][k]+bp[i]*(k-j))\)

于是50分到手。

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define MAXN 2010 using namespace std; int n,m,w; int ap[MAXN],bp[MAXN],as[MAXN],bs[MAXN]; long long dp[MAXN][MAXN]; int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d%d%d",&n,&m,&w);for(int i=1;i<=n;i++)scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)dp[i][j]=-0x3f3f3f3f3f3f3f3f;dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j]=max(dp[i][j],dp[i-1][j]);for(int k=max(0,j-as[i]);k<=j-1;k++){int cur=max(0,i-w-1);dp[i][j]=max(dp[i][j],dp[cur][k]-1ll*ap[i]*(j-k));}for(int k=j+1;k<=m&&k<=j+bs[i];k++){int cur=max(0,i-w-1);dp[i][j]=max(dp[i][j],dp[cur][k]+1ll*bp[i]*(k-j));}}}long long ans=0;for(int i=0;i<=m;i++) ans=max(ans,dp[n][i]);printf("%lld\n",ans);return 0; }

之后我們考慮一下怎么把這個K給去掉。
把轉(zhuǎn)移方程化一下：
\(dp[i][j]=max(dp[i-1][j])\)
\(dp[i][j]=max(dp[i-w-1][k]+k*ap[i])-ap[i]*j (j-as[i]\le k \le j-1)\)
\(dp[i][j]=max(dp[i-w-1][k]+k*bp[i])+bp[i]*j (j+1\le k\le j+bs[i])\)

我們發(fā)現(xiàn)那個取max的部分是可以用單調(diào)隊列優(yōu)化的.......
于是就100pts了

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #define MAXN 2010 using namespace std; int n,m,w; int ap[MAXN],bp[MAXN],as[MAXN],bs[MAXN],q[MAXN]; long long dp[MAXN][MAXN]; int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d%d%d",&n,&m,&w);for(int i=1;i<=n;i++)scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)dp[i][j]=-0x3f3f3f3f3f3f3f3f;for(int i=1;i<=n;i++) dp[i][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=as[i];j++) dp[i][j]=-ap[i]*j;for(int j=0;j<=m;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);if(i-w-1>=0){int head=1,tail=0;for(int j=0;j<=m;j++){while(head<=tail&&q[head]<j-as[i]) head++;while(head<=tail&&dp[i-w-1][j]+ap[i]*j>=dp[i-w-1][q[tail]]+ap[i]*q[tail]) tail--;q[++tail]=j;dp[i][j]=max(dp[i][j],dp[i-w-1][q[head]]-ap[i]*(j-q[head]));}head=1,tail=0;for(int j=m;j>=0;j--){while(head<=tail&&q[head]>j+bs[i]) head++;while(head<=tail&&dp[i-w-1][j]+j*bp[i]>=dp[i-w-1][q[tail]]+q[tail]*bp[i]) tail--;q[++tail]=j;dp[i][j]=max(dp[i][j],dp[i-w-1][q[head]]+bp[i]*(q[head]-j));}}}long long ans=0;for(int i=0;i<=m;i++) ans=max(ans,dp[n][i]);printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/fengxunling/p/10888289.html

總結(jié)

以上是生活随笔為你收集整理的SCOI2010 股票交易的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。