题目链接：传送门
题目：
题目描述 这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入输出格式
输入格式： 第一行为n,m,k（≤n≤,≤m≤,≤k≤），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。 输出格式： 只有一行为k个子矩阵分值之和最大为多少。 输入输出样例
输入样例#： 复制 - - 输出样例#： 复制
PS：好像有很多类似的题目，上次的那道中国象棋（放炮的）也是，都是分类讨论多种情况就好了。
思路：
注意到m ≤ 2，所以可以按行dp，分类讨论转移的情况。
① 当前行不选；
② 当前行选左边；
③ 当前行选右边；
④ 当前行两个都选，但是作为两个矩阵；
⑤ 当前行两个都选，作为同一个矩阵；
以上的m = 2时的情况，m = 1时更简单，只有选或者不选，就不赘述了。
状态：
f[i][j][k] 表示当前第i行，构造了j个矩阵，当前行的状态为k，（k = 0 - 4对应上面的① - ⑤）
状态转移方程很容易得出，见代码。
时间复杂度是O(NM4K)
#include <bits/stdc++.h> using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = + ;
const int MAX_M = + ;
const int MAX_K = + ; inline void tomax(int&a, int b)
{
a = max(a, b);
} int mat[MAX_N][MAX_M];
int f[MAX_N][MAX_K][]; int main()
{
int N, M, K;
cin >> N >> M >> K;
for (int i = ; i <= N; i++)
for (int j = ; j <= M; j++)
scanf("%d", &mat[i][j]);
memset(f, -INF, sizeof f);
for (int i = ; i <= N; i++)
for (int j = ; j <= K; j++)
f[i][j][] = ;
if (M == ) {
for (int i = ; i <= N; i++)
for (int j = ; j <= K; j++) {
tomax(f[i][j][], f[i-][j][]);
tomax(f[i][j][], f[i-][j][]);
if (j- >= )
tomax(f[i][j][], f[i-][j-][]);
tomax(f[i][j][], f[i-][j][]);
f[i][j][] += mat[i][];
}
cout << max(f[N][K][], f[N][K][]) << endl;
return ;
}
for (int i = ; i <= N; i++) {
for (int j = ; j <= K; j++) {
for (int k = ; k <= ; k++) {
//0：当前行不选
tomax(f[i][j][], f[i-][j][k]);
//1：当前行选左边
if ((k == || k == || k == ) && (j- >= ))
tomax(f[i][j][], f[i-][j-][k]);
else if (k == || k == )
tomax(f[i][j][], f[i-][j][k]);
//2：当前行选右边
if ((k <= || k == ) && j- >= )
tomax(f[i][j][], f[i-][j-][k]);
else if (k == || k == )
tomax(f[i][j][], f[i-][j][k]);
//3：当前行左右都选（分开）
if ((k == || k == ) && j- >= )
tomax(f[i][j][], f[i-][j-][k]);
else if ((k == || k == ) && j- >= )
tomax(f[i][j][], f[i-][j-][k]);
else if (k == )
tomax(f[i][j][], f[i-][j][k]);
//4：当前行左右都选（一起的）
if (k != && j- >= )
tomax(f[i][j][], f[i-][j-][k]);
else if (k == )
tomax(f[i][j][], f[i-][j][k]);
}
f[i][j][] += mat[i][];//1：当前行选左边
f[i][j][] += mat[i][];//2：当前行选右边
f[i][j][] += mat[i][] + mat[i][];//3：当前行左右都选（分开）
f[i][j][] += mat[i][] + mat[i][];//4：当前行左右都选（一起的）
}
}
int ans = -INF;
for (int k = ; k <= ; k++)
tomax(ans, f[N][K][k]);
cout << ans;
return ;
}
/*
3 1 2
1
-1
2
*/