bzoj1084: [SCOI2005]最大子矩阵

m<=2，分m==1和m==2的情况讨论，，然后就是一道水DP题，转移见代码

const int N = 110;
int n, m, k, dat[2][N];
int S[4][N];

int f[N][N] = {0};
inline void sol1() {
	For(i, 1, k)
		For(j, 1, n) {
			f[i][j] = f[i][j - 1];
			For(l, 0, j - 1)
				f[i][j] = max(f[i][j], f[i - 1][l] + S[1][j] - S[1][l]);
		}
	printf("%d\n", f[k][n]);
}
int F[N][N][N] = {0};
inline void sol2() {
	For(i, 1, k)
		For(j, 1, n)
			For(l, 1, n) {
				F[i][j][l] =
					max(F[i][j - 1][l - 1], max(F[i][j - 1][l], F[i][j][l - 1]));
				For(p, 0, j - 1)
					F[i][j][l] = max(F[i][j][l], F[i - 1][p][l] + S[1][j] - S[1][p]);
				For(p, 0, l - 1)
					F[i][j][l] = max(F[i][j][l], F[i - 1][j][p] + S[2][l] - S[2][p]);
				if(j == l)
					For(p, 0, l - 1)
						F[i][j][l] = max(F[i][j][l], F[i - 1][p][p] + S[3][l] - S[3][p]);
			}
	printf("%d\n", F[k][n][n]);
}
int main() {
	SetIO("1084");
	
	scanf("%d%d%d", &n, &m, &k);
	For(i, 1, 3)
		For(j, 1, n) S[i][j] = 0;
	For(i, 1, n) {
		For(j, 1, m)
			scanf("%d", &dat[i][j]), S[j][i] = S[j][i - 1] + dat[i][j];
		S[3][i] = S[1][i] + S[2][i];
	}
	
	if(m == 1) sol1();
	else sol2();
	return 0;
}