题目大意:

读入一个n*n的数组,比如

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2 

从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大.

截取出来的矩阵,和为15

9 2

-4 1

-1 8

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

POJ 1050 我的解题报告：

这个题目很经典的说，O（N^3）的DP。

首先偶们考察这样的题目，简化版：

已知一列数，求任意连续若干个数和的最大值。

SAMPLE： 3 2 -6 2 -1 7

原数3         2       -6        2       -1        7

处理3         5       -1        2        1        8

因为是连续若干个自然数的和，那么，前面的某个数字取与不取的条件在于：以前面这个数字为结尾的连续数的和最大值是否大于0，如果大于0，那么这个数字必然要会出现在包括数字的序列中，否则无法做到最大。

所以，显然。处理的原则是maxn[i]=max{0,maxn[i-1]}+a[i];

由于无须记录位置。所以，可以直接用一个变量sum代替maxn数组。O(n)的扫描即可。

单列数字的问题解决了，下面我们考察多列数字的

sample:

          0     -2     -7     0

          9      2     -6     2

         -4      1     -4     1

         -1      8      0    -2

我们可以将多列数字转换成单列数字来做！ 可以这样设想，结果是一个长方形，我们把他压扁，使得宽为1。

引入辅助数组st,st[i][j]代表第i列从第1行开始的数字累加到第j行的值。那么，我们每次压扁的时候，就可以用st[i][j]-st[i][k-1]来表示第i列从第k个数字累加到第j个数字的值。达到压缩的效果。然后用上面单列数字的方法来做。算法时间复杂度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;

}  

original source:http://hi.baidu.com/flymouse/blog/item/fd1378f05c7ff7c37931aac3.html
 

党员之歌
我是党的一条狗，
站在党的大门口。
党叫咬谁就咬谁，
叫咬几口就几口！
昨天

话说2003年4月1日，愚人节，一个反共的共产党员出现了，那就是偶！
从此我入党的日子记得甭提有多熟了。
每当年华老去的时候，我会想起那一天。
每当被人整蛊的时候，我会想起那一天。
就是在那一天以后，以后工资的*%成为了党费。
就是在那一天以后，俺可以骄傲地骂共产党，为啥？因为这是自我反省！
就是在那一天以后，俺爸俺妈可以大声的说：“我不是党员，我儿才是党员！”

今天

师兄拿出一张1元的rmb，露出奇怪的眼神。仔细一看，原来有一面迎着所谓党团的什么宣传口号。
这伙人还真是有创意，利用这个来做宣传，高，实在是高！

这几天访问我的msn space都很奇怪，就是south park那个entry访问不起，一到评论block就马上转该页无法显示。让同学试，也是一样，猜想是评论搞的鬼！GFW！！！通过加密代理浏览一试，果然。两个反共评论！又是党团！

赞一个baidu的效率，高！昨天在baidu hi发的一个<黑砖窑结案了>，今天就被删了。
还是qq zone和msn space好！它好，我也好！

明天

明天？明天就是人的后颈窝，摸的着，看不着，可以有着unlimited imagination!
谁管呢？
只是希望所谓党团不要再来骚扰偶了，只想悄悄对它说：对不起，我是党员！