蒟蒻寻找大佬系列

P1719 最大加权矩形

tsuppari @ 2018-10-06 11:06:04

#include <iostream>
using namespace std;
int f[125][125],b[125];
int main()
{
    int n,m,i,j,k,maxx=0,sum=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>f[j][i];
            maxx+=f[j][i];
        }
    }
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)b[i]=0;
        for(i=k;i<=n;i++)
        {
            sum=0;
            for(j=1;j<=n;j++)
            {   
                b[j]+=f[j][i];
                sum+=b[j];
                if(sum<0)sum=0;

            }
            //for(j=1;j<=n;j++)cout<<b[j]<<" ";
            //cout<<endl;
            maxx=max(maxx,sum);
        }
    }
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)b[i]=0;
        for(i=k;i<=n;i++)
        {
            sum=0;
            for(j=1;j<=n;j++)
            {
                b[j]+=f[i][j];
                sum+=b[j];
                if(sum<0)sum=0;

            }
            //for(j=1;j<=n;j++)cout<<b[j]<<" ";
            //cout<<endl;
            maxx=max(maxx,sum);
        }
    }
    cout<<maxx;
    return 0;
}

by yjc_yjc @ 2018-10-06 11:12:22

我是大佬

by yjc_yjc @ 2018-10-06 11:12:46

该题算是P1115 最大子段和的一个升级版，其实思想差不多，都是DP，只不过该题需要先进行一个矩阵压缩，即二维变一维。

矩阵压缩：

假设有一个矩阵：

-5 6 4

1 -2 6

2 1 -3

如何对它进行压缩呢，其实不难，这边我做一个类比，如果我们把一行看做一个数，这里看做三个数a,b,c,那么将这三个相邻数的进行不同的组合，将这个新的组合视为一个新的数，这就是进行压缩处理，例如a,b,c可以组合为{[a],[ab],[abc],[b],[bc],[c]}，而矩阵压缩也类似。

先设置一个变量max用于保存压缩后的一维数组的最大子序列和。

第一次我们取第一行：

-5 6 4

则其最大子序列和为10，max=10。

第二次取第一二行：

-5 6 4

1 -2 6

注意现在开始是矩阵压缩的精髓，我们将每一列的数进行相加，将多行变为一行。

第一列：-5+1=-4

第二列：6+(-2)=4

第三列：4+6=10

所以压缩后的一维数组为：

-4 4 10

则其最大子序列和为14，max=14。

第三次取第一二三行：

-5 6 4

1 -2 6

2 1 -3

对每一列进行压缩：

第一列：-5+1+2=-2

第二列：6+(-2)+1=5

第三列：4+6+(-3)=7

所以压缩后的一维数组为：

-2 5 7

则其最大子序列和为12，max=14。

第四次取第二行：

1 -2 6

则其最大子序列和为6，max=14。

第五次取第二三行：

1 -2 6

2 1 -3

对每一列进行压缩：

第一列：1+2=3

第二列：-2+1=-1

第三列：6+(-3)=3

所以压缩后的一维数组为：

3 -1 3

则其最大子序列和为5，max=14。

第六次取第三行：

2 1 -3

则其最大子序列和为3，max=14。

最后求得这个矩阵最大的子矩阵和为14

也就是第一二行的三四列

6 4

-2 6

代码：

include <bits/stdc++.h>

define infinitesimal -2100000000

using namespace std; typedef long long int lli; /**

define mset(t, x) memset(t,x,sizeof(t))

define loop(a, b, c) for(int a=b;a<=c;a++)

define loop2(a, b, c) for(int a=b;a>=c;a--)

define loop3(a, b, c) for(int a=b;a<c;a++)

define loop4(a, b, c) for(int a=b;a>c;a--)

define maxn 150

define maxm 20

int n, m, t; int matrix[maxn][maxn]; int ans = infinitesimal; int temp[maxn]; int dp[maxn];

void Arrsum() { mset(dp, 0); loop(i, 1, n) { dp[i] = max(dp[i], dp[i - 1] + temp[i]); ans = max(ans, dp[i]); } }

void MatrixSum() { loop(i, 1, n) { mset(temp, 0); loop(j, i, n) { loop(k, 1, n) { temp[k] += matrix[j][k]; } Arrsum(); } } }

int main() { scanf("%d", &n); loop(i, 1, n) { loop(j, 1, n) { scanf("%d", &matrix[i][j]); } } MatrixSum(); printf("%d\n", ans); return 0; }
希望更丰富的展现？使用Markdown

by yjc_yjc @ 2018-10-06 11:12:49

@凌丶

by zzqDeco @ 2018-10-06 11:13:21

@yjc_yjc 希望更丰富的展现？使用Markdown

by Fraction @ 2018-10-06 11:20:29

@yjc_yjc 直接复制题解的过分了

by 祈佑·绾青鸢 @ 2018-10-06 11:27:06

@yjc_yjc 希望更丰富的展现？使用Markdown

by yjc_yjc @ 2018-10-06 11:32:05

抱歉，本人被盗号，已经修改密码，如有得罪，请见谅。

by tsuppari @ 2018-10-06 16:56:54

QAQ...

by tsuppari @ 2018-10-06 16:57:20

我发现调试的部分和题解的部分是一样的，然后我就懵逼了

by tsuppari @ 2018-10-06 16:57:37

叫上去就听取WA声一片

|