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

            Why so serious? --[NKU]schindlerlee

            pku1505 AC此題分4步

            國(guó)家集訓(xùn)隊(duì)2000論文集/方奇論文中的一題
            1.dp ,算最小完成時(shí)間, 論文中貌似把max寫(xiě)成min了。。
            二分求最小完成時(shí)間亦可,而且更快,誰(shuí)讓咱們看了論文了呢
            for(i = 1;i <= n;i++) {
                dp[1][i] = sum[1][i];
            }
            for(i = 2;i <= m;i++) {
                for(j = 1;j <= n;j++) {
                    dp[i][j] = inf;
                }
            }

            for(i = 2;i <= m;i++) {
                for(j = i;j <= n;j++) {
                    for(k = 1;k < j;k++) { // 至少抄一本
                        int t = max( dp[i-1][k] , sum[k+1][j]);
                        if(dp[i][j] > t) {
                            dp[i][j] = min(dp[i][j] ,t);
                        }
                    }
                }
            }
            2.從后向前推把更大的工作量留給后面的人,標(biāo)記'/'出現(xiàn)的位置

            int limit = dp[m][n],sum,cnt;
            pre[n] = 0,cnt = 1;
            for(i = n-1,sum = num[n];i > 0;i--) {
                if(sum + num[i] > limit) {
                    pre[i] = 1;
                    cnt ++;
                    sum = num[i];
                }else {
                    pre[i] = 0;
                    sum += num[i];
                }
            }
            3.如果'/'的數(shù)量小于題目給出的,從頭尋找第一個(gè)不是'/'的位置,標(biāo)記之
            for(i = 1,j = cnt;j < m && i <= n;i++) {
                if(pre[i] == 0) {
                    pre[i] = 1;
                    j++;
                }
            }
            4.輸出
            for(i = 1;i < n;i++) {
                printf("%d ",num[i]);
                if(pre[i])
                    printf("/ ");
            }
            printf("%d\n",num[i]);

            注意:不要嘗試再dp轉(zhuǎn)移的時(shí)候標(biāo)記轉(zhuǎn)移方向,試圖得出標(biāo)記‘/’的位置,這個(gè)想法是錯(cuò)的,仔細(xì)想一下就知道了,
            再不濟(jì)AC以后再試試

            posted on 2009-09-16 01:32 schindlerlee 閱讀(1238) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告

            精品国产99久久久久久麻豆| 久久久午夜精品| 亚洲成色www久久网站夜月 | 久久精品国产亚洲AV无码偷窥| 日韩人妻无码精品久久免费一| 99久久精品免费看国产一区二区三区 | 久久夜色撩人精品国产| 久久人妻少妇嫩草AV蜜桃| 亚洲国产视频久久| 久久久青草久久久青草| 久久久精品国产| 久久精品免费观看| 亚洲婷婷国产精品电影人久久| 亚洲精品乱码久久久久久蜜桃不卡 | 国产精品久久久久a影院| 久久综合中文字幕| 亚洲AV无码1区2区久久| 国产亚州精品女人久久久久久| 亚洲国产一成人久久精品| 日本精品一区二区久久久| 久久久精品午夜免费不卡| 亚洲欧美伊人久久综合一区二区| 99久久99久久精品免费看蜜桃 | 人人妻久久人人澡人人爽人人精品 | 国产精品99久久久久久猫咪| 久久91精品国产91| 久久中文字幕视频、最近更新 | 中文字幕亚洲综合久久2| 亚洲av日韩精品久久久久久a| 久久无码一区二区三区少妇| 国产精品va久久久久久久| 国产精品久久久天天影视| 久久国产欧美日韩精品| 婷婷五月深深久久精品| 午夜人妻久久久久久久久| 人妻精品久久无码区| 久久久久久国产精品免费无码| 人妻无码αv中文字幕久久 | 久久久久99精品成人片欧美| 久久亚洲欧美国产精品| 日韩AV无码久久一区二区|