随笔-68  评论-10  文章-0  trackbacks-0
题目链接: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 阅读(579) 评论(1)  编辑 收藏 引用 所属分类: 动态规划

评论:
# re: hdu3401(DP+单调队列优化) 2011-08-20 16:45 | twinkle
感谢分享。最后求答案不必枚举i,直接在f[t][0]处。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理