• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            a tutorial on computer science

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              21 隨筆 :: 0 文章 :: 17 評(píng)論 :: 0 Trackbacks
               神題。比較難想的單調(diào)隊(duì)列優(yōu)化。暴力o(N^2)過掉。據(jù)說線段樹(n*logN)會(huì)掛掉。。需要用到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 閱讀(1119) 評(píng)論(0)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            亚洲成人精品久久| 亚洲伊人久久综合影院| 久久精品人妻中文系列| 久久人人爽人人爽人人片av麻烦 | 少妇内射兰兰久久| 久久青青草原亚洲av无码app | 免费精品国产日韩热久久| 久久99热这里只频精品6| 久久久久久精品久久久久| 99久久99久久精品免费看蜜桃| 久久综合久久综合久久| 久久综合久久综合亚洲| 久久精品a亚洲国产v高清不卡| 久久久久久免费视频| 精品免费久久久久国产一区| 青青草原精品99久久精品66| 久久影视综合亚洲| 精品久久综合1区2区3区激情| 欧美一区二区三区久久综合| 狠狠色丁香久久婷婷综合图片| 国产福利电影一区二区三区久久久久成人精品综合 | 精品久久久久久无码国产| 精品国产乱码久久久久久呢| 99久久精品国产一区二区| 久久亚洲精品成人av无码网站| 久久无码AV中文出轨人妻| 99久久精品国产综合一区| 久久99国产精品一区二区| 久久综合噜噜激激的五月天| 久久精品国产男包| 久久99这里只有精品国产| 亚洲AV伊人久久青青草原| 狠狠人妻久久久久久综合蜜桃| 久久伊人精品青青草原高清| 国产精品福利一区二区久久| 亚洲国产欧洲综合997久久| 久久精品国产99国产精品导航| 国产69精品久久久久观看软件| 中文字幕无码久久精品青草| 精品国产乱码久久久久软件| 久久久久久精品无码人妻|