openjudge-NOI 2.6-1768 最大子矩阵

题目链接：http://noi.openjudge.cn/ch0206/1768/

题解：
　　如果用O(n⁴)的算法肯定会炸，需要压缩掉一维的空间，只需要简单加和就好啦

　　例如，我们要对样例中第2-4行DP，就这样压缩：

　　

　　然后利用区间DP中求最大子序列和的状态转移方程f_i=max(f_i-1+a_i,a_i)求解即可

　　代码为了节约空间少记录了一些东西，temp1为当前正在求的这几行的最大结果，temp2为当前的a_i

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110
#define MAX 2147483647
int n,f[MAXN],a[MAXN][MAXN];
int main()
{
    int ans=-MAX;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j]+=a[i-1][j];
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            memset(f,0,sizeof(f));
            int temp1=-MAX;
            for(int k=1;k<=n;k++)
            {
                int temp2=a[j][k]-a[i-1][k];
                f[k]=max(f[k-1]+temp2,temp2);
                temp1=max(temp1,f[k]);
            }
            ans=max(ans,temp1);
        }
    }
    printf("%d
",ans);
    return 0;
}