a tutorial on computer science

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 17 评论 :: 0 Trackbacks
    严重鄙视这一题,弄了N复杂的一个题意。。。做了好多天都没想法,今天终于看着题解把它A掉了。。
    其实单调队列如果再没有明显的 max(i,i+K) 的情况下。。很难想得到。这个题目就是。
    题意是说一个人跟政府关系很好。知道了下面T天每天的股票价格。但是XX告诉他,儿子啊,我告诉你啊,你买股票要这么买,要不会被抓的。你手上的股票数最多不能超过maxP,而且某一天买卖之后,下次买卖的时间必须延后W天,你懂的。好了,下面告诉你T天的价格,你自己赚钱去吧。
    这题的朴素的DP方程是这样的: res[i][j] = res[i-W-1][k]  + 买入或卖出的代价     ( j-ASi<=k <=j+BSi )
    有人会问为什么只枚举了i-W-1天呢?前面的日子呢?额。。。前面的日子已经归到i-W-1天啦。
    好了,这破题。状态复杂度: T*maxP,决策复杂度maxP。无悬念的超时了。
   别人说用单调队列优化就单调队列优化吧。
   我们可以这样想:假如i-w-1天那家伙持有的股票根据那天股票的价格换成了钱,就是都虚拟换成r[i-w-1][0],这样,我们可以知道,我们不会选择钱少的决策的,因为我们现在得j是固定的,当换算后的钱多的时候,无论怎样决策都比钱少的好。。,好了,着就变成了第二句话那样的模型了,直接换算出来,弄个丑陋的单调队列出来,然后唧唧歪哇一大堆。
   下面是代码,写的比较长,比较乱。纠结。。。。纠结。。。。
//单调队列用法:求一段序列里的最值。   加上决策有序    
//这个题 : 决策的时候,把持有的股票数转化出来,可知当决策为 max(res[i-W-1][j-ASi],res[i-W-1][j+BSi]+k*BAi,BPi)时, 


#include 
<stdio.h>
#include 
<string.h>
#define inf 900000

typedef 
struct
{
  
int APi,BPi,ASi,BSi;
}
node;

typedef 
struct
{
  
int pos;
  
int res;
}
qe;
int qhead,qtail;
qe queue[
410010];
node data[
2010];

int res[2010][2010];//第i天拥有j的股票赚的最多的钱

int T,W,maxP;

int max(int i,int j)
{
  
if(i > j) return i;
  
return j;
}


int main()
{
   
int testcase,i,j,k;
   scanf(
"%d",&testcase);
   
while(testcase--)
   
{
     
int ans = 0;
     scanf(
"%d%d%d",&T,&maxP,&W);
     
for(i=1;i<=T;i++)
     
{
       scanf(
"%d%d%d%d",&data[i].APi,&data[i].BPi,&data[i].ASi,&data[i].BSi);    
     }


     
for(i=1;i<=T;i++)
      
for(j=0;j<=maxP;j++)
        res[i][j] 
= -1000000;

     
for(i=1;i<=W+1;i++)
      
for(j=0;j<=data[i].ASi;j++)
        res[i][j] 
= -j*data[i].APi; 

     
for(i=2;i<=T;i++)
     
{
           
for(j=0;j<=maxP;j++)
             res[i][j] 
= max(res[i][j],res[i-1][j]); 
          
           
//由i-w-1天买入,维护在i-w-1天总资产递增序列 
           qhead = qtail = 0;
           
if(i-W-1<1)
             
continue;
           
for(j=0;j<=maxP;j++)
           
{
              qe tmp;
              tmp.pos 
= j,tmp.res = res[i-W-1][j] + j*data[i].APi;
              queue[qhead
++= tmp;
              
while(qhead > qtail + 1 && queue[qhead-1].res > queue[qhead-2].res)
              
{
                qhead
--;
                queue[qhead
-1= tmp;
              }

              
while(qhead > qtail + 1 && data[i].ASi + queue[qtail].pos < j )
                qtail
++;
              res[i][j] 
= max(res[i][j],res[i-W-1][queue[qtail].pos] - data[i].APi * (j - queue[qtail].pos));
           }

           
           qhead 
= qtail = 0;
           
           
for(j=maxP;j>=0;j--)
           
{
             qe tmp;
             tmp.pos 
= j,tmp.res = res[i-W-1][j] + j*data[i].BPi;
             queue[qhead
++= tmp; 
             
while(qhead > qtail + 1 && tmp.res > queue[qhead-2].res)
              
{
                qhead
--;
              }

             queue[qhead
-1= tmp;
             
              
while(qhead > qtail + 1 && queue[qtail].pos - data[i].BSi > j)
                qtail
++;
              res[i][j] 
= max(res[i][j],res[i-W-1][queue[qtail].pos] + data[i].BPi * (queue[qtail].pos - j));
           }
                        
     }
 
    
for(i=0;i<=maxP;i++)
      
if(ans < res[T][i])
        ans 
= res[T][i];
    printf(
"%d\n",ans);   
   }

   
return 0;
}

posted on 2012-03-16 16:16 bigrabbit 阅读(1148) 评论(7)  编辑 收藏 引用

评论

# re: 单调队列优化dp]Problem - 3401 Trade 2012-03-16 16:52 我执分别心
呵呵,玩ACM要有被虐的勇气  回复  更多评论
  

# re: 单调队列优化dp]Problem - 3401 Trade 2012-03-16 16:57 bigrabbit
@我执分别心
额。。同行?欢迎交流。  回复  更多评论
  

# re: 单调队列优化dp]Problem - 3401 Trade 2012-03-16 17:09 crystalBlade
没看到题目,我out了?  回复  更多评论
  

# re: 单调队列优化dp]Problem - 3401 Trade 2012-03-16 17:11 bigrabbit
@crystalBlade
http://acm.hdu.edu.cn/showproblem.php?pid=3401
这是题目。额,你的博客就一篇文章额。。  回复  更多评论
  

# re: 单调队列优化dp]Problem - 3401 Trade 2012-03-16 18:45 远行
一直被虐中,求一个月后人品爆发  回复  更多评论
  

# re: 单调队列优化dp]Problem - 3401 Trade 2012-03-17 09:28 tb
玩ACM要有被虐的勇气 呵呵   回复  更多评论
  

# re: 单调队列优化dp]Problem - 3401 Trade 2012-03-17 10:42 bigrabbit
@tb
你这么卡bug么。。。你的首页变淘宝了。。。  回复  更多评论
  


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