• <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   管理


            色天使久久综合网天天| 国产精久久一区二区三区| 久久久久久久久久久久久久| 午夜精品久久久久久久| 久久99免费视频| 久久久亚洲欧洲日产国码是AV| 久久久老熟女一区二区三区| 久久播电影网| 久久亚洲精品中文字幕| 久久久精品久久久久久| 国产精品99久久久久久人| 一本久道久久综合狠狠躁AV| 韩国三级大全久久网站| 精品久久久一二三区| 国产精品成人精品久久久| 日韩人妻无码精品久久久不卡| 久久毛片免费看一区二区三区| 国产午夜福利精品久久2021| 2021久久精品免费观看| 久久成人18免费网站| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久久久黑人强伦姧人妻| 亚洲va中文字幕无码久久| 久久综合日本熟妇| 久久久久亚洲av成人无码电影| 亚洲综合久久综合激情久久| 久久久久久国产精品免费无码| 久久精品桃花综合| 伊人伊成久久人综合网777| 久久久精品视频免费观看| 九九久久精品无码专区| 日本免费一区二区久久人人澡| 国产91色综合久久免费| 国产成人久久精品激情| 久久久精品人妻一区二区三区蜜桃 | 久久99精品综合国产首页| 久久久国产乱子伦精品作者| 久久综合88熟人妻| 72种姿势欧美久久久久大黄蕉| 97久久天天综合色天天综合色hd| 久久婷婷激情综合色综合俺也去 |