解题报告 P1719 最大加权矩形

题目内容

P1719

大意：给定一个数字矩阵，求最大子矩阵和

解题思路

这题可以使用最大子段和的思想，思想就是合并矩阵，将其降维打击。

每次枚举待合并矩阵的行的上下界，然后开数组将这几行上的数合并，然后取最大子段和。这就是将矩阵降维。

复杂度：枚举上下界的过程是 O(n^2) 的，合并的过程是 O(n^2)，使用前缀和优化后为 O(n)，求最大子段和的复杂度是 O(n)，因此总的复杂度是 O(n^3)。具体见代码：

#include <cstdio>
#include <cstring>

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=125;
int n,s[maxn][maxn],a[maxn][maxn],f[maxn],tmp[maxn];
//s[i][j]存储矩阵第j列的前i行的前缀和，tmp存储合并后的结果，f为dp使用

int getsum()//求最大子段和的
{
    memset(f,0,sizeof(f));//先清零
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=max(f[i-1]+tmp[i],f[i]);//求最大子段和
        ans=max(ans,f[i]);
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            s[i][j]+=s[i-1][j]+a[i][j];//处理这一列的前缀和
        }
    int ans=0;
    for(int i=1;i<=n;i++)//i为上界
        for(int j=i;j<=n;j++)//j为下界
        {
            for(int k=1;k<=n;k++)//O(n)合并
                tmp[k]=s[j][k]-s[i-1][k];
            ans=max(ans,getsum());//统计答案
        }
    printf("%d\n",ans);
    return 0;
}