BZOJ原题链接
洛谷原题链接
注意该题的子矩阵可以是空矩阵，即可以不选，答案的下界为(0)。
设(f[i][j][k])表示前(i)行选择了(j)个子矩阵，选择的方式为(k)时的最大分值之和。
- (k = 0)表示该行不选数。
- (k = 1)表示该行只选左边的数。
- (k = 2)表示该行只选右边的数。
- (k = 3)表示该行选两个数，但分别属于两个子矩阵。
- (k = 4)表示该行选两个数，属于一个子矩阵。
设一行中左边的数为(x)，右边的数为(y)。
- (k = 0)时
直接由上一层转移来：$$f[i][j][0] = max{ f[i][j][0], f[i - 1][j][0], f[i - 1][j][1], f[i - 1][j][2], f[i - 1][j][3], f[i - 1][j][4] }$$
- (k = 1)时
若上层状态为(1)或(3)，则可以直接接上去，其它的都需要另开一个子矩阵：$$f[i][j][1] = max{ f[i][j][1], max{ f[i - 1][j - 1][0], f[i - 1][j][1], f[i - 1][j - 1][2], f[i - 1][j][3], f[i - 1][j - 1][4] } + x}$$
- (k = 2)时
若上层状态为(2)或(3)，则可以直接接上去，其它的都需要另开一个子矩阵：$$f[i][j][2] = max{ f[i][j][2], max{ f[i - 1][j - 1][0], f[i - 1][j - 1][1], f[i - 1][j][2], f[i - 1][j][3], f[i - 1][j - 1][4] } + y}$$
- (k = 3)时
若上层状态为(3)，则可以直接接上去，若为(0)或(4)，则需要另开两个子矩阵，其它的都需要另开一个子矩阵：$$f[i][j][3] = max{ f[i][j][3], max{ f[i - 1][j - 2][0], f[i - 1][j - 1][1], f[i - 1][j - 1][2], f[i - 1][j][3], f[i - 1][j - 2][4] } + x + y }$$
- (k = 4)时
若上层状态为(4)，则可以直接接上去，其它的都需要另开一个子矩阵：$$f[i][j][4] = max{ f[i][j][4], max{ f[i - 1][j - 1][1], f[i - 1][j - 1][2], f[i - 1][j - 1][3], f[i - 1][j][4] } + x + y }$$
(f)直接初始化全为(0)，因为可以取空矩阵，即不选数。
最后答案为(max{ f[n][k][0], f[n][k][1], f[n][k][2], f[n][k][3], f[n][k][4] })。
在(DP)过程中注意判断边界，部分状态对宽度或是子矩阵个数有要求。
因为没开循环，所以代码及其难看。。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 110;
int f[N][12][5], a[N][N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
inline void ckmaxn(int &x, int y)
{
if (x < y)
x = y;
}
int main()
{
int i, j, n, m, k;
n = re();
m = re();
k = re();
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
a[i][j] = re();
for (i = 1; i <= n; i++)
for (j = 1; j <= k; j++)
{
ckmaxn(f[i][j][0], maxn(f[i - 1][j][0], f[i - 1][j][1]));
ckmaxn(f[i][j][1], maxn(f[i - 1][j - 1][0], f[i - 1][j][1]) + a[i][1]);
if (m > 1)
{
ckmaxn(f[i][j][0], maxn(f[i - 1][j][2], f[i - 1][j][4]));
ckmaxn(f[i][j][1], maxn(f[i - 1][j - 1][2], f[i - 1][j - 1][4]) + a[i][1]);
ckmaxn(f[i][j][2], maxn(maxn(f[i - 1][j - 1][0], f[i - 1][j - 1][1]), maxn(f[i - 1][j][2], f[i - 1][j - 1][4])) + a[i][2]);
ckmaxn(f[i][j][4], maxn(maxn(f[i - 1][j - 1][0], f[i - 1][j - 1][1]), maxn(f[i - 1][j - 1][2], f[i - 1][j][4])) + a[i][1] + a[i][2]);
if (j > 1)
{
ckmaxn(f[i][j][0], f[i - 1][j][3]);
ckmaxn(f[i][j][1], f[i - 1][j][3] + a[i][1]);
ckmaxn(f[i][j][2], f[i - 1][j][3] + a[i][2]);
ckmaxn(f[i][j][3], maxn(maxn(f[i - 1][j - 2][0], maxn(f[i - 1][j - 1][1], maxn(f[i - 1][j - 1][2], f[i - 1][j][3]))), f[i - 1][j - 2][4]) + a[i][1] + a[i][2]);
ckmaxn(f[i][j][4], f[i - 1][j - 1][3] + a[i][1] + a[i][2]);
}
}
}
printf("%d", maxn(maxn(f[n][k][0], f[n][k][1]), maxn(f[n][k][2], maxn(f[n][k][3], f[n][k][4]))));
return 0;
}