• <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>
            posts - 195,  comments - 30,  trackbacks - 0
            [原創(chuàng)]POJ1050 To the Max 解題報(bào)告
            2006-04-17 11:55
            題目大意:

            讀入一個(gè)n*n的數(shù)組,比如 

            0 -2 -7 0 

            9 2 -6 2 

            -4 1 -4 1 

            -1 8 0 -2  

            從里面任意截取一個(gè)矩陣,使得矩陣所包含的數(shù)字的和最大.

            截取出來的矩陣,和為15

            9 2 

            -4 1 

            -1 8 

            ---------------------------------------------------------

            POJ 1050 我的解題報(bào)告:

            這個(gè)題目很經(jīng)典的說,O(N^3)的DP。

            首先偶們考察這樣的題目,簡化版:

            已知一列數(shù),求任意連續(xù)若干個(gè)數(shù)和的最大值。

            SAMPLE: 3 2 -6 2 -1 7

            原數(shù)3        2      -6       2      -1       7 

            處理3        5      -1       2       1       8

            因?yàn)槭沁B續(xù)若干個(gè)自然數(shù)的和,那么,前面的某個(gè)數(shù)字取與不取的條件在于:以前面這個(gè)數(shù)字為結(jié)尾的連續(xù)數(shù)的和最大值是否大于0,如果大于0,那么這個(gè)數(shù)字必然要會(huì)出現(xiàn)在包括數(shù)字的序列中,否則無法做到最大。

            所以,顯然。處理的原則是maxn[i]=max{0,maxn[i-1]}+a[i];

            由于無須記錄位置。所以,可以直接用一個(gè)變量sum代替maxn數(shù)組。O(n)的掃描即可。

            單列數(shù)字的問題解決了,下面我們考察多列數(shù)字的

            sample:

                     0    -2    -7    0 

                     9     2    -6    2 

                    -4     1    -4    1 

                    -1     8     0   -2 



            我們可以將多列數(shù)字轉(zhuǎn)換成單列數(shù)字來做! 可以這樣設(shè)想,結(jié)果是一個(gè)長方形,我們把他壓扁,使得寬為1。

            引入輔助數(shù)組st,st[i][j]代表第i列從第1行開始的數(shù)字累加到第j行的值。那么,我們每次壓扁的時(shí)候,就可以用st[i][j]-st[i][k-1]來表示第i列從第k個(gè)數(shù)字累加到第j個(gè)數(shù)字的值。達(dá)到壓縮的效果。然后用上面單列數(shù)字的方法來做。算法時(shí)間復(fù)雜度O (N^3)

            Source



            Problem Id:1050  User Id:galaxy 

            Memory:112K  Time:0MS

            Language:G++  Result:Accepted



            /*

              Name:POJ 1050 

              Copyright: flymouse@galaxy                                         

              Author:chenlei

              Date: 15-02-06 07:36

              Description: DP O(N^3)

            */

            #include <stdio.h>

            #include <string.h>

            #define mt 101

            int main()

            {

            int a[mt][mt];

            int st[mt][mt];

            int p,k,n,i,j,sum,maxn;

            //freopen("in.txt","r",stdin);

            scanf("%d",&n);

            for (i=1;i<=n;i++)

            for (j=1;j<=n;j++)

            scanf("%d",&a[i][j]);

            memset(st,0,sizeof(st));

            for (i=1;i<=n;i++)

               for (j=1;j<=n;j++)

              st[i][j]=st[i][j-1]+a[j][i];

              maxn=0;

               for (i=1;i<=n;i++)

               {

            for (j=i;j<=n;j++)

            {

            p=st[1][j]-st[1][i-1];

            sum=p;

            for (k=2;k<=n;k++)

            {

            if (sum>0)

            sum+=st[k][j]-st[k][i-1];

            else sum=st[k][j]-st[k][i-1];

            if (sum>p) p=sum;

            }

            if (p>maxn) maxn=p;

            }

               }

               printf("%d\n",maxn);

               return 0;
            原文地址:http://hi.baidu.com/flymouse/blog/item/fd1378f05c7ff7c37931aac3.html
            posted on 2009-07-09 18:37 luis 閱讀(322) 評論(0)  編輯 收藏 引用 所屬分類: 動(dòng)態(tài)規(guī)劃轉(zhuǎn)載
            <2012年12月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久91精品国产91| 国产精品久久久久久| 久久久国产视频| 亚洲av成人无码久久精品| 久久精品国产亚洲欧美| 久久久久久国产精品美女| 99久久国产亚洲综合精品| 久久国产亚洲高清观看| 久久青青草原精品国产软件| 久久伊人精品一区二区三区| 久久福利青草精品资源站| 三级三级久久三级久久| 青青青青久久精品国产| 亚洲AV伊人久久青青草原| 久久青青草原综合伊人| 亚洲国产精品无码久久一线| 久久久国产精华液| 日韩精品久久久久久| 中文字幕乱码人妻无码久久| 国产精品成人99久久久久91gav| 国产成人精品三上悠亚久久| 色综合久久88色综合天天| 伊人久久大香线焦AV综合影院| 国产精品日韩深夜福利久久| 天堂久久天堂AV色综合| 亚洲欧洲精品成人久久曰影片| 蜜桃麻豆www久久| 久久精品国产精品青草app| 色综合久久久久综合体桃花网| 亚洲国产一成久久精品国产成人综合| 伊人丁香狠狠色综合久久| 国产精品美女久久久久久2018 | 久久精品中文字幕一区| 精品无码久久久久久久久久| 久久九九精品99国产精品| 无码专区久久综合久中文字幕 | 久久综合综合久久综合| 久久久精品久久久久久| 久久精品国产精品亜洲毛片| 国产精品一久久香蕉国产线看| 99久久免费国产精品特黄|