Trade
题目:http://acm.hdu.edu.cn/showproblem.php?pid=3401
题意:知道之后n天的股票买卖价格(api,bpi),以及每天股票买卖数量上限(asi,bsi),问他最多能赚多少钱。开始时有无限本金,要求任两次交易需要间隔W天以上,即第i天交易,第i+w+1天才能再交易。同时他任意时刻最多只能拥有maxp的股票,
题解:容易写出DP方程 dp[i][j]=max{dp[i-1][j],max{dp[r][k]-APi[i]*(j-k)}(0<r<i-w,k<j),max{dp[r][k]+BPi[i]*(k-j)}(0<r<i-w,k>j)} 分别是第i天不交易,买股票和卖股票3种转移。
第一眼看会发现这个方程十分冗杂,没有下手的地方。我们可以分析下,对于买卖股票的转移中的dp[r][k]中的r是否有枚举的价值,注意dp[i][j]中取最大时会考虑dp[i-1][j]的值,也就是dp[i-w-1][k]>=dp[r][k](0<r<i-w)恒成立。这样就省去了r 的枚举,但这还不够。以买股票为例,我们可以化简max{dp[i-w-1][k]-APi[i]*(j-k)}(k<j)},即dp[i-w-1][k]-APi[i]*(j-k)=dp[i-w-1][k]+APi[i]*k-APi[i]*j(k<j),可以发现对于确定的i和j只要取符合条件中最大的dp[i-w-1][k]+APi[i]*k即可,这个可以通过单调队列实现。
代码:
#include<cstdio> #include<cstring> using namespace std; #define MAX 2005 #define inf 0xfffff #define max(a,b) ((a)>(b)?(a):(b)) int T,MaxP,W; int APi[MAX],BPi[MAX],ASi[MAX],BSi[MAX]; int dp[MAX][MAX];//dp[i][j]第i天持有j股的最大值 //dp[i][j]=max{dp[i-1][j],max{dp[r][k]-APi[i]*(j-k)}(0<r<i-w,k<j),max{dp[r][k]+BPi[i]*(k-j)}(0<r<i-w,k>j)} struct node { int x;//存dp[i-w-1][k]+APi[i]*k或dp[i-w-1][k]+BPi[i]*k int p;//当前持股数 } q[2005],temp; int front,back; int main() { int cas; scanf("%d",&cas); for(; cas--;) { scanf("%d%d%d",&T,&MaxP,&W); for(int i=1; i<=T; ++i) scanf("%d%d%d%d",APi+i,BPi+i,ASi+i,BSi+i); for(int i=0; i<=T; ++i) for(int j=0; j<=MaxP; ++j) dp[i][j]=-inf; for(int i=1; i<=W+1; ++i) for(int j=0; j<=ASi[i]; ++j) dp[i][j]=(-APi[i]*j); for(int i=2; i<=T; ++i) { for(int j=0; j<=MaxP; ++j) dp[i][j]=max(dp[i][j],dp[i-1][j]); if(i<=W+1) continue; //买入 front=back=1; for(int j=0; j<=MaxP; ++j) { temp.p=j; temp.x=dp[i-W-1][j]+APi[i]*j; for(;front<back&&q[back-1].x<temp.x;--back); q[back++]=temp; for(;front<back&&q[front].p+ASi[i]<j;++front); dp[i][j]=max(dp[i][j],q[front].x-APi[i]*j); } //卖出 front=back=1; for(int j=MaxP; j>=0; --j) { temp.p=j; temp.x=dp[i-W-1][j]+BPi[i]*j; for(;front<back&&q[back-1].x<temp.x;--back); q[back++]=temp; for(;front<back&&q[front].p-BSi[i]>j;++front); dp[i][j]=max(dp[i][j],q[front].x-BPi[i]*j); } } int ans=0; for(int i=0;i<=MaxP;++i) ans=max(ans,dp[T][i]); printf("%d\n",ans); } return 0; }
来源:http://blog.csdn.net/acm_ted/article/details/7909742