题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3401用f[i][j]表示第i天股票数为j的最大收益，f[i][j]可以从以下三个地方得到：
1、在上次交易的基础上再买一些: f[i][j]=max{f[i][j],f[r][k]-(j-k)*b_price[i]} 0<r<i-w, 0<=j-k<=b_num[i]
2、在上次交易的基础上卖出一些: f[i][j]=max{f[i][j],f[r][k]+(k-j)*s_price[i]} 0<r<i-w, 0<=k-j<=s_num[i]
3、当天股票不动: f[i][j]=max{f[i][j],f[i-1][j]}
这样的时间复杂度为O(T^2*MaxP^2)，需要做一些优化.
对于买股票的时候，f[r][k]-(j-k)*b_price[i]=f[r][k]+k*b_price[i]-j*b_price[i] ,(j>= k>=j-b_num[i]),f[i][j]的最优值由f[r][k]+k*b_price[i]确定，由递推方程可知，f[r][k]始终是股票数为k的最大值. 对于某个j，f[r][k]+k*b_price[i]已经重复求过了，这次只需要求f[r][j]+j*b_price[i]即可,因此可以用单调队列来保存这些信息,并且可以方便的取出最大值。 卖股票的情况也同上面类似。此时的时间复杂度为O(T*MaxT).
#include<iostream>
#define max(a,b) (a>b?a:b)
using namespace std;
const int inf=0x7fffffff;
int test,t,maxp,w;
int b_price[2005],s_price[2005];
int b_num[2005],s_num[2005];
int f[2005][2005];
typedef struct node
{
int mon,num;
}NODE;
NODE q[2005];
int main()
{
scanf("%d",&test);
while(test--)
{
scanf("%d%d%d",&t,&maxp,&w);
for(int i=1;i<=t;i++)
scanf("%d%d%d%d",&b_price[i],&s_price[i],&b_num[i],&s_num[i]);
for(int i=0;i<=t;i++)
for(int j=0;j<=maxp;j++)
f[i][j]=-inf;
for(int i=1;i<=w+1;i++)
for(int j=0;j<=maxp&&j<=b_num[i];j++)
f[i][j]=-j*b_price[i];
for(int i=2;i<=w+1;i++)
for(int j=0;j<=maxp;j++)
f[i][j]=max(f[i-1][j],f[i][j]);
for(int i=w+2;i<=t;i++)
{
int head=0,tail=0;
for(int j=0;j<=maxp;j++)
{
f[i][j]=max(f[i][j],f[i-1][j]);
int pre=i-w-1;
int money=f[pre][j]+j*b_price[i];
while(head<tail&&q[tail-1].mon<money) tail--;
q[tail].mon=money;
q[tail++].num=j;
while(head<tail&&j-q[head].num>b_num[i]) head++;
f[i][j]=max(f[i][j],q[head].mon-j*b_price[i]);
}
head=tail=0;
for(int j=maxp;j>=0;j--)
{
int pre=i-w-1;
int money=f[pre][j]+j*s_price[i];
while(head<tail&&q[tail-1].mon<money) tail--;
q[tail].mon=money;
q[tail++].num=j;
while(head<tail&&q[head].num-j>s_num[i]) head++;
f[i][j]=max(f[i][j],q[head].mon-j*s_price[i]);
}
}
int ans=-inf;
for(int i=0;i<=maxp;i++)
if(f[t][i]>ans) ans=f[t][i];
printf("%d\n",ans);
}
//system("pause");
return 0;
}
posted on 2010-08-27 18:38
wuxu 阅读(568)
评论(1) 编辑 收藏 引用 所属分类:
动态规划