• <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>
            隨筆 - 68  文章 - 57  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(8)

            隨筆分類(74)

            隨筆檔案(68)

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

              給定n個數(shù)求這n個數(shù)劃分成互不相交的m段的最大m子段和。
              經(jīng)典的動態(tài)規(guī)劃優(yōu)化的問題。設(shè)f(i, j)表示前i個數(shù)劃分成j段,且包括第i個數(shù)的最大m子段和,那么有dp方程:
                f(i, j) = max { f(i - 1, j) + v[i], max {f(k, j - 1) + v[i]}(k = j - 1 ... i - 1) }
              也就是說第i個數(shù)要么自己劃到第j段,要么和前一個數(shù)一起劃到第j段里面,轉(zhuǎn)移是O(n)的,總復(fù)雜度O(n * n * m)。
              可以引入一個輔助數(shù)組來優(yōu)化轉(zhuǎn)移。設(shè)g(i, j)表示前i個數(shù)劃分成j段的最大子段和(注意第i個數(shù)未必在j段里面),那么遞推關(guān)系如下:
                g(i, j) = max{g(i - 1, j), f(i, j)},分是否加入第i個數(shù)來轉(zhuǎn)移
              這樣f的遞推關(guān)系就變成:
                f(i, j) = max{f(i - 1, j), g(i - 1, j - 1)} + v[i],轉(zhuǎn)移變成了O(1)
              這樣最后的結(jié)果就是g[n][m],通過引入輔助數(shù)組巧妙的優(yōu)化了轉(zhuǎn)移。實現(xiàn)的時候可以用一維數(shù)組,速度很快。

            附HDU 1024題目代碼:
            #include <cstdio>
            #include 
            <algorithm>
            using namespace std;
            const int N = 1000010, INF = 0x3fffffff;

            int f[N], g[N], a[N];

            int max_sum(int m, int n)
            {
                
            int i, j, t;
                
            for (i = 1; i <= n; i++)
                {
                    t 
            = min(i, m);
                    
            for (j = 1; j <= t; j++)
                    {
                        f[j] 
            = max(f[j], g[j-1]) + a[i];
                        g[j
            -1>?= f[j-1];
                    }
                    g[j
            -1>?= f[j-1];
                }
                
            return g[m];
            }

            int main()
            {
                
            int m, n;

                
            while (scanf("%d %d"&m, &n) == 2 && m && n)
                {
                    
            for (int i = 1; i <= n; i++)
                    {
                        f[i] 
            = g[i] = -INF;
                        scanf(
            "%d"&a[i]);
                    }
                    printf(
            "%d\n", max_sum(m, n));
                }

                
            return 0;
            }
            posted on 2009-06-19 11:18 sdfond 閱讀(4879) 評論(4)  編輯 收藏 引用 所屬分類: Algorithm - Dynamic Programming

            FeedBack:
            # re: 最大M子段和 2010-04-24 10:27 qq258513813
            能不能給我更詳細點呢? 動態(tài)規(guī)劃感覺比較難理解,這方面沒有什么基礎(chǔ),好急哦。  回復(fù)  更多評論
              
            # re: 最大M子段和 2010-04-24 18:36 sdfond
            @qq258513813
            我分析過程寫的很詳細了,實現(xiàn)的時候降了一維,你要是知道背包問題如何實現(xiàn)的話這個就不難理解,如果實在理解不了,就先把最基礎(chǔ)的那些學(xué)了吧,最大字段和、子矩陣、子立方體什么的,我感覺我已經(jīng)不能更詳細了-_-!  回復(fù)  更多評論
              
            # re: 最大M子段和 2011-03-16 17:55 阿皮
            學(xué)習(xí)了, 謝謝  回復(fù)  更多評論
              
            # re: 最大M子段和[未登錄] 2012-09-20 10:58 Bill
            @阿皮
            可以看這個鏈接http://blog.163.com/sentimental_man/blog/static/7300161820119109533172/
            比作者的詳細很多。  回復(fù)  更多評論
              
            久久综合久久鬼色| 久久99精品久久久久久齐齐 | 激情五月综合综合久久69| 日韩精品久久久久久免费| 久久人人爽人人爽人人片AV麻烦| 亚洲国产天堂久久综合| 亚洲国产精品狼友中文久久久| 99久久www免费人成精品 | 亚洲狠狠久久综合一区77777| 久久精品人人槡人妻人人玩AV | 精品乱码久久久久久夜夜嗨| 99久久国产综合精品网成人影院 | 久久婷婷色综合一区二区| 亚洲性久久久影院| 麻豆精品久久久久久久99蜜桃| 亚洲精品乱码久久久久久不卡| 精品久久久久久久国产潘金莲| 一本色道久久综合狠狠躁篇| 亚洲va久久久噜噜噜久久狠狠 | 99久久精品国产免看国产一区| 97久久精品无码一区二区天美| 国产精品久久久久影院色| 91精品无码久久久久久五月天| 欧美久久综合九色综合| 麻豆精品久久久久久久99蜜桃| www性久久久com| 国内精品伊人久久久久影院对白| 一本色道久久综合狠狠躁篇| 无码国内精品久久人妻蜜桃| 久久免费小视频| 欧美粉嫩小泬久久久久久久 | 久久精品国产久精国产| 久久一区二区三区99| 午夜人妻久久久久久久久| 99久久精品免费看国产一区二区三区| 久久久久亚洲AV无码专区网站| 久久综合亚洲色HEZYO社区| 久久er热视频在这里精品| 亚洲va久久久久| 蜜桃麻豆www久久| 亚洲国产精品一区二区久久hs|