首页 > 代码库 > hdu3401 Trade(单调队列优化dp)
hdu3401 Trade(单调队列优化dp)
TradeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4734 Accepted Submission(s): 1587 Problem Description Recently, lxhgww is addicted to stock, he finds some regular patterns after a few days‘ study. He forecasts the next T days‘ stock market. On the i‘th day, you can buy one stock with the price APi or sell one stock to get BPi. There are some other limits, one can buy at most ASi stocks on the i‘th day and at most sell BSi stocks. Two trading days should have a interval of more than W days. That is to say, suppose you traded (any buy or sell stocks is regarded as a trade)on the i‘th day, the next trading day must be on the (i+W+1)th day or later. What‘s more, one can own no more than MaxP stocks at any time. Before the first day, lxhgww already has infinitely money but no stocks, of course he wants to earn as much money as possible from the stock market. So the question comes, how much at most can he earn? Input The first line is an integer t, the case number. The first line of each case are three integers T , MaxP , W . (0 <= W < T <= 2000, 1 <= MaxP <= 2000) . The next T lines each has four integers APi，BPi，ASi，BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above. Output The most money lxhgww can earn. Sample Input 15 2 02 1 1 12 1 1 13 2 1 14 3 1 15 4 1 1 Sample Output 3 Author lxhgww Source HDOJ Monthly Contest – 2010.05.01 Recommend lcy | We have carefully selected several similar problems for you: 3400 3403 3404 3402 3415 | |||
|
题目大意：知道之后n天的股票买卖价格（api，bpi），以及每天股票买卖数量上限（asi，bsi），问他最多能赚多少钱。开始时有无限本金，要求任两次交易需要间隔W天以上，即第i天交易，第i+w+1天才能再交易。同时他任意时刻最多只能拥有maxp的股票，
/*1. dp[i][j] 表示前 i 天手里有 j 支股票时所获得的最大收益，因为要间隔 w+1 天才能进行一次买卖所以前 w+1 天只能进行一个操作，那就是买操作。2. 关于赋初值问题，合法的状态也有可能为负值的，而且结果要取最大值所以非法状态要赋值为 -INFS.3. dp[i][j] = max(dp[i-w-1][x] - (j-x)*AP, dp[i-w-1][y] + (y-j)*BP); 另外还有第 i 天什么都不做的情况此时为 dp[i][j] = max(dp[i][j], dp[i-1][j]).4. 关于转移方程，时间复杂度是很高的，所以要采取单调队列优化deq[],pos[] 分别放置窗口里面的最大值以及最大值所在的窗口位置。这里用了一个结构体的队列直接维护这两个信息5. 如何构造单调队列里面的转移，其实很简单例如 dp[3] = max(dp[1] + 2 * v, dp[2] + 1 * v); 两边同时减去 3 * v 就可以变成一个通项公式了，偏移正好。高中数学知识。6.推到队列优化也可以这样做，只考虑买的情况，卖的和它对称。dp[i][j] = max(dp[i-w-1][k]-j*ap[i]+k*ap[i]),移下项变成dp[i][j]+j*ap[i]=max(dp[i-w-1][k]+k*ap[i])，很明显可以把后面维护成一个递减的单调队列，每次取队首元素，使得复杂度降为O(N*P)*/#include<cstdio>#include<cstring>#define MAX 2005#define inf 0xfffff#define max(a,b) ((a)>(b)?(a):(b))using namespace std;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;}
hdu3401 Trade(单调队列优化dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。