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

            2010年02月13日星期六.sgu183 根據(jù)單調(diào)性優(yōu)化的dp

            2010年02月13日星期六.sgu183
            sgu183:根據(jù)單調(diào)性優(yōu)化的dp
            一開始想的挺好,二維狀態(tài),第一維是染第i個(gè),第二維表示染了第i-j個(gè)。
            題目要求要在任何的連續(xù)m個(gè)球中都有兩個(gè)染色的,那么邊界條件就是
            染了第i個(gè),i-m個(gè),和他們中間的某個(gè),這樣就能抱枕任何的連續(xù)m個(gè)球都有兩個(gè)。

            然后寫了個(gè)dp,華麗麗的tle@test 50 ...
             1 const int N = 10010;
             2 const int M = 101;
             3 const int inf = 1 << 30;
             4 int cost[N], n, m;
             5 int dp[N][M];
             6 
             7 int main()
             8 {
             9     int i, j, k;
            10     scanf("%d%d"&n, &m);
            11     for (i = 1; i <= n; i++) {
            12         scanf("%d", cost + i);
            13     }
            14     for (i = 0; i < N; i++) {
            15         for (j = 0; j < M; j++) {
            16             dp[i][j] = inf;
            17         }
            18     }
            19     dp[0][0= 0;
            20     for (i = 1; i <= n + 1; i++) {
            21         for (j = 0; i - j >= 0 && j <= m; j++) {    
            22             for (k = 0; i - j - k >= 0 && j + k <= m; k++) {    
            23                 if (dp[i - j][k] < inf) {
            24                     dp[i][j] = min(dp[i][j], dp[i - j][k] + cost[i]);
            25                 }
            26             }
            27         }
            28     }
            29     int res = inf;
            30     for (j = 0; j <= m; j++) {
            31         res = min(res, dp[n + 1][j]);
            32     }
            33     printf("%d\n", res);
            34 
            35 }

            這也難怪,復(fù)雜度是N * M * M = 10 ^ 9;
            然后我就像,可怎么辦。我就開始憋。
            觀察上面的dp可以看出 dp[i][j]是按照從j從小到達(dá)的順序計(jì)算的,
            而k也是按照從小到達(dá)轉(zhuǎn)移的,也就是
            dp[i][j] 來自dp[i-j][0],dp[i-j][1]...dp[i-j][i-m]
            那么我們就可以讓dp[i][j] 保存dp[i][0] ...dp[i][j]的最小值,那么
            在后來的轉(zhuǎn)移時(shí)用到dp[i][j]當(dāng)做邊界時(shí)只需要O(1) 的轉(zhuǎn)移了。總的復(fù)雜度就變成了
            N*M = 10 ^ 7 ,恩應(yīng)該沒問題了。

            更形象話的解釋

            dp[i-j][0] dp[i-j][1] ... dp[i-j][i-m]
            dp[i][j]逐一檢查上述的值,選出最小的。

            現(xiàn)在dp[i][j] 表示dp[i][0 ... j]中的最小值.

            dp[i][j]只要檢查檢查dp[i-j][i-m] 和 dp[i][j-1]即可。
             1 
             2 const int N = 10010;
             3 const int M = 101;
             4 const int inf = 1 << 30;
             5 int cost[N], n, m;
             6 int dp[N][M];
             7 
             8 int main()
             9 {
            10     int i, j, k;
            11     scanf("%d%d"&n, &m);
            12     for (i = 1; i <= n; i++) { scanf("%d", cost + i); }
            13     for (i = 1; i < N; i++) {
            14         for (j = 0; j < M; j++) {
            15             dp[i][j] = inf;
            16         }
            17     }
            18     for (j = 0; j < M; j++) { dp[0][j] = 0; }
            19     for (i = 1; i <= n + 1; i++) {
            20         for (j = 1; i - j >= 0 && j <= m; j++) {    
            21             int k = (i > m) ? m-j : i-j;
            22             if (dp[i-j][k] < inf) {
            23                 dp[i][j] = dp[i-j][k] + cost[i];
            24             }
            25             if (dp[i][j] > dp[i][j-1])
            26               dp[i][j] = dp[i][j-1];
            27         }
            28     }
            29     printf("%d\n", dp[n+1][m]);
            30 }
            31 
            32 


            posted on 2010-02-13 02:23 schindlerlee 閱讀(1642) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告

            精品无码久久久久久久动漫| 久久久久久伊人高潮影院| 久久99九九国产免费看小说| 丁香五月综合久久激情| 久久国产成人午夜AV影院| 国产欧美一区二区久久| 国产精品成人99久久久久91gav| 无码人妻久久一区二区三区免费丨 | 一本大道久久香蕉成人网| 国产精品久久久久久五月尺| 久久人人爽人人爽人人片AV麻豆 | 中文字幕久久欲求不满| 四虎影视久久久免费| 日本人妻丰满熟妇久久久久久| 久久99国产精品久久99| 色综合久久综合网观看| 亚洲欧美日韩中文久久| 久久久一本精品99久久精品66 | 久久夜色精品国产噜噜亚洲AV| 久久综合久久自在自线精品自| 国产精品久久久久无码av| 久久久久久国产精品无码下载| 亚洲va久久久噜噜噜久久狠狠| 久久精品国产亚洲av影院| 66精品综合久久久久久久| 欧美日韩中文字幕久久久不卡| 精品国产乱码久久久久久人妻| 2020久久精品国产免费| 久久久久无码专区亚洲av| 亚洲精品无码久久久久| 99久久成人18免费网站| 漂亮人妻被中出中文字幕久久| 久久精品国产亚洲av日韩| 国产L精品国产亚洲区久久| 色老头网站久久网| 成人a毛片久久免费播放| 亚洲欧洲精品成人久久曰影片| 国产精品久久久久天天影视 | 欧美一级久久久久久久大片| 久久久久久九九99精品| 久久久久亚洲精品中文字幕|