Trade
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2817 Accepted Submission(s): 890
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?
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.
1 5 2 0 2 1 1 1 2 1 1 1 3 2 1 1 4 3 1 1 5 4 1 1
3
题意：炒股……规定每天最多买进多少，卖出多少，并且每次炒股后隔w天才能再次炒股，问最大收益。
思路：
首先想到最朴素的dp。dp[i][j]代表第i天有j股会带来最大收益。
则dp[i][j] = max(dp[i-1][j], dp[r][k]-(j-k)ap[i], dp[r][k]+(k-j)bp[i]); 复杂度是O(T*T*Maxp*Maxp)。
首先想到第一步优化，前面式子r范围是0~i-w-1，怎么优化呢，因为dp[i][j]至少为dp[i-1][j]，那么dp[i-w-1][k] >= dp[...][k]恒成立（...指r的范围内的数）
故dp[i][j] = max(dp[i-1][j], dp[i-w-1][k]-(j-k)ap[i], dp[i-w-1][k]+(k-j)bp[i]); 复杂度是O(T*Maxp*Maxp)。还是很大。
接下来就是单调队列的作用了，dp[i][j] = max(dp[i-1][j], (dp[i-w-1][k]+k*ap[i])-j*ap[i], (dp[i-w-1][k]+k*bp[i])-j*bp[i]);
对于每一个j。j*ap[i]或j*bp[i]相同。所以取其前或后的(dp[i-w-1][k]+k*ap[i])或(dp[i-w-1][k]+k*bp[i])的最大值就行。最大值用单调队列维护
这题开始初始化写错了。找bug找了n久。差点还输顿饭钱。不过最后还是自己找出来了。看来坚持不懈是对的。dp路依然漫长。。。加油！
#include <iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define positive(a) ((a)>0?(a):-(a))
using namespace std;
int ap[2010],bp[2010],as[2010],bs[2010];
int dp[2010][2010];
int t,w,head,tail,mp;
int ans;
struct node
{
int val;
int id;
} q[2010];
void solve()
{
int i,j,buy,sell,limit;
memset(dp,0xcf,sizeof dp);//初始为负无穷大。
for(i=1; i<=w+1; i++)//前w+1天只能买或不买。
{
limit=MIN(as[i],mp);
for(j=0; j<=limit; j++)//第i天购入的情况但dp[i][j]未必最优
{
dp[i][j]=-ap[i]*j;//初始为第i天购入j股的花费。但应该为第i天拥有j股的最大价值
//dp[i][j]=MAX(dp[i][j],dp[i-1][j]);无效。因为第i天拥有的股票大于as[i]这样超过as[i]的部分就不能更新了
}
}
for(i=2; i<=t; i++)//必须从2开始
{
if(i<=w+1)//保证dp[i][j]为第i天拥有j股的最大价值而不是购入价格
{
for(j=0;j<=mp;j++)
dp[i][j]=MAX(dp[i][j],dp[i-1][j]);
continue;
}
head=0;
tail=-1;
for(j=0; j<=mp; j++)//买入
{
dp[i][j]=MAX(dp[i][j],dp[i-1][j]);
buy=dp[i-w-1][j]+j*ap[i];
while(tail>=head&&buy>=q[tail].val)
tail--;
q[++tail].id=j;
q[tail].val=buy;
while(j-q[head].id>as[i])//买入不能超过as[i]
head++;
dp[i][j]=MAX(dp[i][j],q[head].val-j*ap[i]);
}
head=0;
tail=-1;
for(j=mp; j>=0; j--)//卖出
{
sell=dp[i-w-1][j]+j*bp[i];
while(tail>=head&&sell>=q[tail].val)
tail--;
q[++tail].id=j;
q[tail].val=sell;
while(q[head].id-j>bs[i])//卖出不能超过bs[i]
head++;
dp[i][j]=MAX(dp[i][j],q[head].val-j*bp[i]);
}
}
ans=0;
for(i=0; i<=mp; i++)
if(dp[t][i]>ans)
ans=dp[t][i];
}
int main()
{
int i,cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d%d",&t,&mp,&w);
for(i=1; i<=t; i++)
scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
solve();
printf("%d\n",ans);
}
return 0;
}