P1719题解

liyifan24 · 2018-08-16 18:03:53 · 题解

这道题挺水的，呵呵，讲白了就是求最大子矩阵， 方法么，学过线性动态规划的同学们应该简单的吧，基础啊！这题其实可以优化的，就用前缀和，具体看一下代码， 走起：

#include <iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
LL G[550][550];
int main()
{
    int m,n,i,j,k;
    LL a[550],dp[550],maxn,x;
    scanf("%d%d",&m,&n);
    memset(G,0,sizeof(G));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%lld",&x);
            G[i][j]=G[i-1][j]+x;//每行的前缀和
        }
    }
    maxn=0;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            dp[0]=0;
            for(k=1;k<=m;k++)
            {
                a[k]=G[j][k]-G[i-1][k];
                dp[k]=max(a[k],a[k]+dp[k-1]);
                maxn=max(maxn,dp[k]);
            }
        }
    }
    printf("%lld",maxn);
    return 0;
}

好了，一道水题。。。。。