我是大佬
by yjc_yjc @ 2018-10-06 11:12:22
该题算是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;
}
希望更丰富的展现？使用Markdown
by yjc_yjc @ 2018-10-06 11:12:46
@[凌丶](/space/show?uid=100055)
by yjc_yjc @ 2018-10-06 11:12:49
@[yjc_yjc](/space/show?uid=81451) 希望更丰富的展现？使用Markdown
by zzqDeco @ 2018-10-06 11:13:21
@[yjc_yjc](/space/show?uid=81451) 直接复制题解的过分了
by Fraction @ 2018-10-06 11:20:29
@[yjc_yjc](/space/show?uid=81451) 希望更丰富的展现？使用Markdown
by 祈佑·绾青鸢 @ 2018-10-06 11:27:06
抱歉，本人被盗号，已经修改密码，如有得罪，请见谅。
by yjc_yjc @ 2018-10-06 11:32:05
QAQ...
by tsuppari @ 2018-10-06 16:56:54
我发现调试的部分和题解的部分是一样的，然后我就懵逼了
by tsuppari @ 2018-10-06 16:57:20
叫上去就听取WA声一片
by tsuppari @ 2018-10-06 16:57:37