洛谷 P2569 [SCOI2010] 股票交易

本文主要是介绍洛谷 P2569 [SCOI2010] 股票交易，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源于：洛谷

题目本质：动态规划，单调队列

解题思路：

方程f[i][j]表示第 i 天结束后，手里剩下 j 股的最大利润，则不买不卖：f[i][j]=f[i-1][j]。

买入：f[i][j]=max{f[i-w-1][k]+k*ap[i]}-ap[i]*j

卖出：f[i][j]=max{f[i-w-1][k]+k*bp[i]}-bp[i]*j

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int t,maxp,w;
int ap[N],bp[N],as[N],bs[N];
int f[N][N];
int q[10000],qhead=1,qtail=0;
int main(){scanf("%d%d%d",&t,&maxp,&w);for(int i=1;i<=t;i++){scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);}memset(f,-0x7f,sizeof(f));for(int i=0;i<=t;i++){f[i][0]=0;}for(int i=1;i<=t;i++){for(int j=0;j<=as[i];j++){f[i][j]=-ap[i]*j;}for(int j=maxp;j>=0;j--){f[i][j]=max(f[i][j],f[i-1][j]);}if(i-w-1>=0){qhead=1;qtail=0;for(int j=0;j<=maxp;j++){while(qhead<=qtail&&q[qhead]<j-as[i]){qhead++;}while(qhead<=qtail&&f[i-w-1][j]+ap[i]*j>=f[i-w-1][q[qtail]]+ap[i]*q[qtail]){qtail--;}q[++qtail]=j;if(qhead<=qtail){f[i][j]=max(f[i][j],f[i-w-1][q[qhead]]-ap[i]*(j-q[qhead])); }} qhead=1;qtail=0;for(int j=maxp;j>=0;j--){while(qhead<=qtail&&q[qhead]>j+bs[i]){qhead++;}while(qhead<=qtail&&f[i-w-1][j]+bp[i]*j>=f[i-w-1][q[qtail]]+bp[i]*q[qtail]){qtail--;}q[++qtail]=j;if(qhead<=qtail){f[i][j]=max(f[i][j],f[i-w-1][q[qhead]]+bp[i]*(q[qhead]-j));}} } }int ans=0;for(int i=0;i<=maxp;i++){ans=max(f[t][i],ans);}printf("%d",ans);return 0;
}

这篇关于洛谷 P2569 [SCOI2010] 股票交易的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---