題目大意:

讀入一個(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;