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

            misschuer

            常用鏈接

            統計

            積分與排名

            百事通

            最新評論

            poj 2393 Yogurt factory

            //用單調隊列優化
            #include <iostream>
            #define MAXV 10001
            using namespace std;

            typedef 
            struct {

                __int64 val;
                
            int in;
            }point;

            point q[MAXV];
            __int64 staf[MAXV];
            __int64 cost[MAXV];
            __int64 dp[MAXV], n;
            __int64 c;

            void res() {

                
            int s = 0, e = -1;
                dp[ 
            0 ] = 0;
                point p, pt;

                
            for(int i = 1; i <= n; ++ i) {
                
                    p.
            in = i;
                    p.val 
            = cost[ i ];

                    
            while(s <= e) {
                    
                        pt 
            = q[ e ];

                        
            if(pt.val + c * (i - pt.in< p.val) break;
                            
                        e 
            --;
                    }
                    
                    
            ++ e;        q[ e ] = p;          pt = q[ s ];
                    dp[ i ] 
            =  dp[i - 1+ staf[ i ] * (pt.val + c * (i - pt.in));
                }

                printf(
            "%I64d\n", dp[ n ]);
            }

            int main() {

                
            while(~scanf("%d %I64d"&n, &c)) {
                
                    
            for(int i = 1; i <= n; ++ i)
                        scanf(
            "%I64d %I64d"&cost[ i ], &staf[ i ]);

                    res();
                }
                
            return 0;
            }

            posted on 2011-03-27 20:22 此最相思 閱讀(249) 評論(0)  編輯 收藏 引用

            久久国产免费观看精品| 狠狠久久综合| 久久精品中文无码资源站| 一本久久知道综合久久| 91精品国产高清久久久久久io | 久久精品中文字幕有码| 国产69精品久久久久观看软件| 青青草原精品99久久精品66| 久久精品国产99国产电影网| 日韩va亚洲va欧美va久久| 久久久久久综合网天天| 2020最新久久久视精品爱| 久久久久亚洲AV成人网人人网站| 2021少妇久久久久久久久久| 中文字幕无码久久人妻| 欧美日韩中文字幕久久伊人| 狠狠色丁香久久婷婷综合蜜芽五月| 99热成人精品热久久669| 伊人色综合九久久天天蜜桃| 久久国产精品99精品国产987| 久久久久精品国产亚洲AV无码| 久久99国产精品久久久| 伊人久久大香线蕉亚洲五月天| 久久久久国产一区二区| 狠狠色丁香久久婷婷综| 人妻少妇久久中文字幕| 久久精品国产久精国产一老狼| 欧美精品一区二区久久| 国产亚州精品女人久久久久久| 精品午夜久久福利大片| 久久久久久久久无码精品亚洲日韩| 久久天天躁狠狠躁夜夜2020一| 亚洲精品WWW久久久久久| 久久久久黑人强伦姧人妻| 狠狠人妻久久久久久综合| 国产精品女同久久久久电影院 | 久久久久国产亚洲AV麻豆| 日本福利片国产午夜久久| 久久久国产精品网站| 狠狠色丁香婷婷久久综合不卡| 久久精品欧美日韩精品|