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

            久久久这里只有精品加勒比| 无码精品久久一区二区三区 | 色欲综合久久中文字幕网| 久久久亚洲欧洲日产国码二区| 国产午夜久久影院| 欧洲国产伦久久久久久久| 日日躁夜夜躁狠狠久久AV| 热RE99久久精品国产66热| 午夜精品久久久久久久久| 精品久久久久久久久久中文字幕| 77777亚洲午夜久久多人| 久久久精品波多野结衣| 四虎国产精品免费久久5151| 无码国内精品久久人妻蜜桃| 国产精久久一区二区三区| 国产成人久久精品二区三区| av色综合久久天堂av色综合在| 色综合久久天天综合| 亚洲中文字幕无码久久2020| 伊人久久精品影院| 一本一本久久a久久精品综合麻豆| 久久影院综合精品| 99久久精品国产一区二区| 欧美激情精品久久久久久| 精品乱码久久久久久夜夜嗨| 国产精品久久久久jk制服| 2021精品国产综合久久| 久久久久久免费一区二区三区 | 一本色道久久99一综合| 久久97久久97精品免视看| 久久综合九色综合精品| 青青青青久久精品国产h| 91精品国产高清久久久久久io| 欧美丰满熟妇BBB久久久| 麻豆一区二区99久久久久| 一本色综合网久久| 精品少妇人妻av无码久久| 国产精品久久久久久久久鸭| 久久精品www人人爽人人| 免费国产99久久久香蕉| 久久精品18|