【题解】

当$m=1$的时候，$f_{i,j}$表示$1~i$中选取$j$个子矩阵，然后$O(n)$转移

当$m=2$的时候，$f_{i,j,k}$表示第一列$1~i$第二列$1~j$选取$k$个子矩阵，然后$O(n)$转移

总复杂度$O(n^4)$

# include <stdio.h>
# include <algorithm>

using namespace std;

int n, m, K;
int g[110][110], a[110], b[110], f[110][110][110];


int main() {
	scanf("%d%d%d", &n, &m, &K);
	if(m == 1) {
		for (int i=1; i<=n; ++i) scanf("%d", &a[i]), a[i] += a[i-1];
		for (int i=1; i<=n; ++i) 
			for (int j=1; j<=K; ++j) {
				g[i][j] = g[i-1][j];
				for (int k=i-1; k>=0; --k)
					g[i][j] = max(g[i][j], g[k][j-1] + a[i] - a[k]);
			}
		printf("%d\n", g[n][K]);
	} else {
		for (int i=1; i<=n; ++i) scanf("%d%d", &a[i], &b[i]), a[i] += a[i-1], b[i] += b[i-1];
		for (int i=1; i<=n; ++i)
			for (int j=1; j<=n; ++j)
				for (int k=1; k<=K; ++k) {
					f[i][j][k] = max(f[i-1][j][k], f[i][j-1][k]);
					for (int x=1; x<i; ++x)
						f[i][j][k] = max(f[i][j][k], f[x][j][k-1] + a[i] - a[x]);
					for (int y=1; y<j; ++y) 
						f[i][j][k] = max(f[i][j][k], f[i][y][k-1] + b[j] - b[y]);
					if(i == j) {
						for (int x=1; x<i; ++x)
							f[i][j][k] = max(f[i][j][k], f[x][x][k-1] + a[i] - a[x] + b[i] - b[x]);
					}
				}
		printf("%d\n", f[n][n][K]);
	}
	return 0;
}