自动搬运

查看原文

来自洛谷，原作者为

	Yaser **

搬运于2025-08-24 21:28:17，当前版本为作者最后更新于2018-04-25 10:33:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

该题算是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;
/**
 *  Created with IntelliJ Clion.
 *  @author  wanyu
 *  @Date: 2018-04-24
 *  @Time: 08:43
 *  To change this template use File | Settings | File Templates.
 * 
 */

#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;
}