a tutorial on computer science

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 17 评论 :: 0 Trackbacks
   神题。比较难想的单调队列优化。暴力o(N^2)过掉。据说线段树(n*logN)会挂掉。。需要用到BST。额。。。惭愧了。贴出代码先。
#include <stdio.h>

int N;
__int64 M;
int data[100100];
__int64 sum[
100100];
int queue[100100],qhead,qtail;
__int64 res[
100100];

__int64 min(__int64 a,__int64 b)
{
  
if(a > b)
    
return b; 
  
return a;
}

int main()
{
   
int i,j;
   
while(scanf("%d%I64d",&N,&M)!=EOF)
   
{
     
int OK = 1;
     
for(i=1;i<=N;i++)
     
{
        scanf(
"%d",&data[i]);
        
if(data[i] > M)
          OK 
= 0;
        sum[i] 
= sum[i-1+ data[i];
     }

     qhead 
= qtail = 0;
     
int st = 1;
     
for(i=1;i<=N;i++)
     
{
        
while(qhead != qtail && data[i] > data[queue[qhead-1]])    
          qhead
--;
            queue[qhead
++= i;
        
while(sum[i] - sum[st-1> M)
          st
++;
    
        
//[st,i] <=M
        while(qhead != qtail && queue[qtail] < st)
          qtail
++;
         res[i] 
= res[st-1+ data[queue[qtail]]; 
        
        
for(j=qtail;j<qhead-1;j++)
        
{
          res[i] 
= min(res[i],res[queue[j]] + data[queue[j+1]] );
        }

     }
 
     
if(OK == 1)
        printf(
"%I64d\n",res[N]);
     
else
    printf(
"-1\n");
   }

   
return 0;
}


posted on 2012-03-19 18:37 bigrabbit 阅读(1112) 评论(0)  编辑 收藏 引用

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