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

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            伊人久久综在合线亚洲2019| 国产精品综合久久第一页| 久久久久久综合网天天| 国产99久久久国产精品小说| 久久久久久久久波多野高潮| 国产一级做a爰片久久毛片| 久久久久亚洲精品天堂久久久久久 | 伊人久久大香线蕉AV色婷婷色| 伊人久久久AV老熟妇色| 成人久久精品一区二区三区| 久久天天躁狠狠躁夜夜2020老熟妇 | 久久久久亚洲av成人网人人软件| 精品久久久久久无码中文字幕一区 | 性高朝久久久久久久久久| 久久人妻少妇嫩草AV无码专区| 国产精品美女久久久久av爽| 人妻无码αv中文字幕久久| 久久九色综合九色99伊人| 久久九九精品99国产精品| 中文成人无码精品久久久不卡 | 99久久精品免费看国产一区二区三区| 久久人人爽人人爽人人片av高请| 久久亚洲视频| 狠狠色丁香婷婷综合久久来来去| 久久精品国产亚洲AV电影| 日本WV一本一道久久香蕉| 久久亚洲国产精品123区| 亚洲国产成人久久综合一| www.久久热.com| 99久久精品毛片免费播放| 国产精品一区二区久久国产| 久久综合给合久久国产免费| 日韩精品久久久肉伦网站 | 精品一区二区久久| 91精品国产色综合久久| 91精品国产综合久久婷婷| 久久久国产精品亚洲一区| 97久久久久人妻精品专区| 2021久久精品国产99国产精品| 99久久久国产精品免费无卡顿 | 久久精品天天中文字幕人妻|