給定一個 n × m 的矩陣（1 ≤ n ≤ 100, 1 ≤ m ≤ 2, 1 ≤ k ≤ 10），需選出 k 個不重疊的子矩陣，使其分值總和最大。子矩陣不可相互重疊，元素分值絕對值不超過 32767。
n, m, k，接著 n 行矩陣元素分值。k 個子矩陣分值之和的最大值。Input: 3 2 2 1 -3 2 3 -2 3 Output: 9
本題屬於經典區間 DP，利用二維前綴和快速計算任意子矩陣的分值和，再以 DP 狀態 f[i][j] 或 g[i][j][l] 表示前 i 行、選 j 個子矩陣的最大值。由於 m ≤ 2，可分情況討論優化。
m = 1：退化為一維區間選取，f[i][j] 表示前 i 行選 j 段的最大值。m = 2：需考慮兩欄的組合，g[i][j][l] 表示前 i 行第一欄、前 j 行第二欄選 l 段的最大值。利用前綴和 s[i][col] 快速得到區間和，枚舉轉移點 h 更新 DP 值：
f[i][j] = max(f[i-1][j], f[h][j-1] + s[i][1] - s[h][1]) (0 ≤ h < i)
g[i][j][l] = max(
g[i-1][j][l], g[i][j-1][l],
g[h][j][l-1] + s[i][1] - s[h][1],
g[i][h][l-1] + s[j][2] - s[h][2],
(i==j) ? g[h][h][l-1] + s[i][1]-s[h][1] + s[j][2]-s[h][2] : -inf
)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
const int maxn = 105;
int n, m, k;
int f[maxn][15], g[maxn][maxn][15], s[maxn][3];
inline int read() {
int x=0, f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return x*f;
}
int main() {
n=read(); m=read(); k=read();
memset(s, 0, sizeof(s));
F(i,1,n) F(j,1,m) s[i][j] = s[i-1][j] + read();
if (m == 1) {
memset(f, 0, sizeof(f));
F(i,1,n) F(j,1,k) {
f[i][j] = f[i-1][j];
F(h,0,i-1) f[i][j] = max(f[i][j], f[h][j-1] + s[i][1] - s[h][1]);
}
printf("%d\n", f[n][k]);
} else {
memset(g, 0, sizeof(g));
F(i,1,n) F(j,1,n) F(l,1,k) {
g[i][j][l] = max(g[i-1][j][l], g[i][j-1][l]);
F(h,0,i-1) g[i][j][l] = max(g[i][j][l], g[h][j][l-1] + s[i][1] - s[h][1]);
F(h,0,j-1) g[i][j][l] = max(g[i][j][l], g[i][h][l-1] + s[j][2] - s[h][2]);
if (i == j) F(h,0,i-1) g[i][j][l] = max(g[i][j][l], g[h][h][l-1] + s[i][1]-s[h][1] + s[j][2]-s[h][2]);
}
printf("%d\n", g[n][n][k]);
}
return 0;
}
O(n³·k)，在 n≤100, k≤10 範圍內可通過。O(n²·k)。O(1) 區間求和。m=1/2 分類討論，降低狀態維度。
