[洛谷P2331]最大子矩阵
/ / 阅读耗时 14 分钟难度：提高+/省选-
题目描述
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入输出格式
输入格式：
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出格式：
只有一行为k个子矩阵分值之和最大为多少。
输入输出样例
Sample input
3 2 2
1 -3
2 3
-2 3
Sample output
9
题解
首先好好读题，m只能取1或2（坑了很多人了！）。
由于构造数据的缘故，本题考虑和不考虑空矩阵（分值为0）都是可以的。如果考虑空矩阵，题意即为选取不超过k个不重叠的子矩阵使得分值之和最大。介绍两种解法，其中第一种解法不考虑空矩阵，第二种考虑。
- 辣鸡解法（也就是我第一次的解法）
我第一次AC本题时用的方法，时间空间复杂度都很高。但是因为数据量太小，轻松水过~
思路是矩阵先划分再分配。如果规定dp(x1,y1,x2,y2,p)表示从坐标(x1，y1)到(x2，y2)的矩阵区域中选取p个子矩阵时的分值最大值，那么在p>1时，一定可以将这p个子矩阵划分到两个区域中。既可以横向划分（有x2-x1种情况）也可以纵向划分（y1≠y2时才可以划分，显然这时仅有1种情况），之后再对这两个划分区域进行子矩阵数量的分配，注意分配时不要超出区域最大承受的范围（因为没有考虑空矩阵）。本方法难点在于如何求解p=1时的情况，思路是先用dp手段求连续区间的最大值（要限制左端点），需要求三次（第一列，第二列以及两列对应元素和），再在这些dp数据中找到最大值即可。注意到这里找最大值是一个区间最值问题，用ST表维护。总体时间复杂度O(kn3m2)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
using namespace std;
int dp[100][2][100][2][11] = {0}, dp2[2][100][100], op[100][2], op2[100] = {0}, dp3[100][100], n, m, k;
int ST[2][100][100][10], ST2[100][100][10];
int Log[101], bin[10];
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> op[i][j];
dp2[j][i][i] = op[i][j];
op2[i] += op[i][j];
}
for (int i = 0; i < n; i++) {//求区间连续最大值
for (int j = i; j < n; j++) {
if (j == i)dp2[0][i][i] = op[i][0], dp2[1][i][i] = op[i][1], dp3[i][j] = op2[i];
else {
if (dp2[0][i][j - 1] < 0)dp2[0][i][j] = op[j][0];
else dp2[0][i][j] = op[j][0] + dp2[0][i][j - 1];
if (dp2[1][i][j - 1] < 0)dp2[1][i][j] = op[j][1];
else dp2[1][i][j] = op[j][1] + dp2[1][i][j - 1];
if (dp3[i][j - 1] < 0)dp3[i][j] = op2[j];
else dp3[i][j] = op2[j] + dp3[i][j - 1];
}
ST[0][i][j][0] = dp2[0][i][j], ST[1][i][j][0] = dp2[1][i][j], ST2[i][j][0] = dp3[i][j];
}
}
Log[0] = -1, bin[0] = 1;
for (int i = 1; i <= 100; i++)Log[i] = Log[i / 2] + 1;
for (int i = 1; i < 10; i++)bin[i] = bin[i - 1] * 2;//ST表初始化
for (int i = 0; i < n; i++)
for (int j = 1; j <= Log[n]; j++)
for (int p = i; p < n; p++)
if (p + bin[j] <= n) {
ST[0][i][p][j] = max(ST[0][i][p][j - 1], ST[0][i][p + bin[j - 1]][j - 1]);
ST[1][i][p][j] = max(ST[1][i][p][j - 1], ST[1][i][p + bin[j - 1]][j - 1]);
ST2[i][p][j] = max(ST2[i][p][j - 1], ST2[i][p + bin[j - 1]][j - 1]);
}
for (int l = 1; l <= k; l++) {//数量枚举
for (int x1 = 0; x1 < n; x1++) {
for (int y1 = 0; y1 < m; y1++) {
for (int x2 = x1; x2 < n; x2++) {
for (int y2 = y1; y2 < m; y2++) {
dp[x1][y1][x2][y2][l] = -0x7fffffff;
if (l == 1) {
int len = x2 - x1 + 1;
if (y1 == 0)
dp[x1][y1][x2][y2][l] = max(ST[0][x1][x1][Log[len]],
ST[0][x1][x2 - bin[Log[len]] + 1][Log[len]]);
if (y2 == 1)
dp[x1][y1][x2][y2][l] = max(dp[x1][y1][x2][y2][l], max(ST[1][x1][x1][Log[len]],
ST[1][x1][x2 - bin[Log[len]] +
1][Log[len]]));
if (y1 != y2)
dp[x1][y1][x2][y2][l] = max(dp[x1][y1][x2][y2][l], max(ST2[x1][x1][Log[len]],
ST2[x1][x2 - bin[Log[len]] +
1][Log[len]]));
} else {
for (int i = x1; i < x2; i++) {
int last = min(l, (i - x1 + 1) * (y2 - y1 + 1));
for (int j = max(0, l - (x2 - i) * (y2 - y1 + 1)); j <= last; j++)//分配
dp[x1][y1][x2][y2][l] = max(dp[x1][y1][x2][y2][l],
dp[x1][y1][i][y2][j] + dp[i + 1][y1][x2][y2][l - j]);
}
if (y1 != y2) {
int last = min(l, x2 - x1 + 1);
for (int i = max(0, l + x1 - x2 - 1); i <= last; i++)
dp[x1][y1][x2][y2][l] = max(dp[x1][y1][x2][y2][l],
dp[x1][0][x2][0][i] + dp[x1][1][x2][1][l - i]);
}
}
}
}
}
}
}
cout<<dp[0][0][n - 1][m - 1][k];
return 0;
}
- 更好的解法
划分为m=1和m=2两种情况。m=1时就是一个改编的连续区间和最值问题，直接上DP求出即可。方法是令dp(x，p)表示在序号为1~x（从1开始计数）的区间中找到不超过p个连续子区间分值之和的最大值，那么有状态转移方程：
S(a，b)为[a，b]的分值之和，用前缀和维护。初始化dp(1，i)=max(0,value(1,1))(1≤i≤k)，其余为0，递推即可。答案即为dp(n，k)。
m=2时令dp(i，j，p)表示从第一列前i行，第二列前j行组成的区域中选取不超过p个子矩阵的分值之和最大值。在末行元素不选时有：
这里类似最长公共子序列的解法。而选取第一列末行元素时有：
S1(a，b)表示第一列区间[a，b]的分值之和，同样用前缀和维护。同理可得选取第二列末行元素时有：
S2维护第二列区间分值之和。特殊地，在i=j时，可以将它们同时选取，分到同一个子矩阵中：
从它们当中找到最大值即可，初始化方法类似m=1时的情形。答案即为dp(n，n，k)，时间复杂度为O(knm+1)。这种方法代码量较小，效率较高。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
int op[101][3], dp1[101][11] = {0}, dp2[101][101][11] = {0}, sum[3][101] = {0};
int n, m, k;
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> op[i][j];
if (i == 1)sum[j][i] = op[i][j];//前缀和
else sum[j][i] = sum[j][i - 1] + op[i][j];
}
}
if (m == 1) {
for (int i = 1; i <= k; i++)dp1[1][i] = max(0, op[1][1]);
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
for (int p = i - 1; p >= 0; p--) {
dp1[i][j] = max(dp1[i][j], dp1[p][j - 1] + sum[1][i] - sum[1][p]);
dp1[i][j] = max(dp1[i][j], dp1[p][j]);
}
}
}
cout << dp1[n][k];
} else {
for (int i = 1; i <= k; i++)dp2[0][1][i] = max(0, op[1][2]), dp2[1][0][i] = max(0, op[1][1]);
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (!i && !j)continue;
for (int p = 1; p <= k; p++) {
if (i > 0)dp2[i][j][p] = max(dp2[i][j][p], dp2[i - 1][j][p]);//不选的情况
if (j > 0)dp2[i][j][p] = max(dp2[i][j][p], dp2[i][j - 1][p]);
for (int z = i - 1; z >= 0; z--)//第一列枚举
dp2[i][j][p] = max(dp2[i][j][p], dp2[z][j][p - 1] + sum[1][i] - sum[1][z]);
for (int z = j - 1; z >= 0; z--)//第二列枚举
dp2[i][j][p] = max(dp2[i][j][p], dp2[i][z][p - 1] + sum[2][j] - sum[2][z]);
if (i == j) {
for (int z = i - 1; z >= 0; z--)//全枚举
dp2[i][j][p] = max(dp2[i][j][p],
dp2[z][z][p - 1] + sum[1][i] - sum[1][z] + sum[2][i] - sum[2][z]);
}
}
}
}
cout << dp2[n][n][k];
}
return 0;
}