题目大意：给一个n*n的矩阵，矩阵每个元素为一个整数，求权值和最大的子矩阵。
题目分析：这是求最大连续子序列和的二维版本。所以我们可以先看看一维情况：求一个序列的最大连续子序列和。
很显然可以朴素O(n^2)解决这个问题，但是如果我们利用前缀和的话，可以做到O(n)。dp[i]表示前i个数最大连续子序列。那么有方程：dp[i] = max(dp[i - 1] + a[i],a[i])。即要么这个最大连续子序列包含a[i]或者不包含a[i]。
然后再回到二维情况：很显然可以朴素O(n^4)解决这个问题。枚举矩阵的所有子矩阵就可以了。不过这样时空复杂度太高，不妨参照一维情况优化：枚举前i行，dp[i][j][k]表示前i行从第j列到第k列最大子矩阵。那么显然有dp[i][j][k] = max(dp[i - 1][j][k] + a[i][k] - a[i][j - 1],a[i][k] - a[i][j - 1])，其中a[i][j]表示原矩阵中第i行前j列和。这样问题就可以O(n^3)时间解决了。
再仔细看看转移方程，不难发现其实dp数组还可以省掉一维，因为每个dp[i][j][k]只需要知道dp[i - 1][j][k]就可以了，所以dp数组第一维可以去掉。
详情请见代码：
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 101;
int lcm[N][N],dp[N][N][N];
int n;
int main()
{
int i,j,k;
while(scanf("%d",&n) != EOF)
{
memset(dp,0,sizeof(dp));
memset(lcm,0,sizeof(lcm));
for(i = 1;i <= n;i ++)
for(j = 1;j <= n;j ++)
scanf("%d",&lcm[i][j]),lcm[i][j] += lcm[i][j - 1];
int ans = -100000;
for(i = 1;i <= n;i ++)
{
for(j = 1;j <= n;j ++)
{
for(k = j;k <= n;k ++)
{
dp[i][j][k] = max(lcm[i][k] - lcm[i][j - 1],lcm[i][k] - lcm[i][j - 1] + dp[i - 1][j][k]);
ans = max(dp[i][j][k],ans);
}
}
}
printf("%d\n",ans);
}
return 0;
}