[luoguP2331] [SCOI2005]最大子矩陣（DP）

傳送門

?

orz不會做。。。

?

一個好理解的做法（n^3*k）：

分n=1和n=2兩種情況考慮。

n=1時，預處理出前綴和sum[]。

設f[i][j]為到達第i格，已經放了j個子矩陣的最大和，

那么每次先把f[i][j]的值設為f[i-1][j]（第i個元素不屬于第j個子矩陣）

剩下的情況就是第i個元素屬于第j個子矩陣了。

這時候用max(f[h-1][j-1]+(sum[i]-sum[h-1]), 1<=h<=i)更新f[i][j]的最大值，即枚舉第j個子矩陣的起始點。

最終答案為f[m][k]。（邊界條件為f[0][j]=0，包含空矩陣）

n=2時，預處理出分別列的前綴和sum1[],sum2[]。

設f[i][j][l]為在第1列到達第i格，第2列到達第j格，已經放了l個子矩陣的最大和，

那么每次先把f[i][j][l]的值設為max(f[i-1][j][l],f[i][j-1][l])（第i行第1列不屬于子矩陣或第j行第2列不屬于子矩陣，兩者取較大值）

剩下的情況就是第i行第1列和第j行第2列都屬于子矩陣了。

分兩種情況：

一、第i行第1列和第j行第2列屬于不同的子矩陣

分別枚舉第i行第1列所在子矩陣的起始點和第j行第2列所在子矩陣的起始點并更新答案，

即用max(f[h-1][j][l-1]+(sum1[i]-sum1[h-1]), 1<=h<=i)和max(f[i][h-1][l-1]+(sum2[j]-sum2[h-1]),1<=h<=j)更新f[i][j]的最大值。

二、第i行第1列和第j行第2列屬于同一子矩陣

僅當i==j時才包含這種情況（因為i和j要作為當前狀態中子矩陣的末尾）。這時候這個子矩陣的列數必定為2。

還是一樣枚舉子矩陣的起始點，

在i==j的條件下用max(f[h-1][h-1][l-1]+(sum1[i]-sum1[h-1])+(sum2[j]-sum2[h-1]),1<=h<=i)更新答案。

最后答案為f[m][m][k]（邊界條件為f[0][0][l]=0，包含空矩陣）

?

#include <cstdio>
#define M 15
#define N 105 
#define max(x, y) ((x) > (y) ? (x) : (y))int n, m, K;
int sum[N][M];
int f[N][N][M], f0[N][M];int main()
{int i, j, k, l, x;scanf("%d %d %d", &n, &m, &K);for(i = 1; i <= n; i++)for(j = 1; j <= m; j++){scanf("%d", &x);sum[i][j] = sum[i - 1][j] + x;}if(m == 1){for(i = 1; i <= n; i++)for(j = 1; j <= K; j++){f0[i][j] = f0[i - 1][j];for(k = 1; k <= i; k++)f0[i][j] = max(f0[i][j], f0[k - 1][j - 1] + sum[i][1] - sum[k - 1][1]);}printf("%d\n", f0[n][K]);return 0;}for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)for(k = 1; k <= K; k++){f[i][j][k] = max(f[i - 1][j][k], f[i][j - 1][k]);for(l = 1; l <= i; l++)f[i][j][k] = max(f[i][j][k], f[l - 1][j][k - 1] + sum[i][1] - sum[l - 1][1]);for(l = 1; l <= j; l++)f[i][j][k] = max(f[i][j][k], f[i][l - 1][k - 1] + sum[j][2] - sum[l - 1][2]);if(i == j)for(l = 1; l <= i; l++)f[i][i][k] = max(f[i][i][k], f[l - 1][l - 1][k - 1] + sum[i][1] - sum[l - 1][1] + sum[i][2] - sum[l - 1][2]);}printf("%d\n", f[n][n][K]);return 0;
}

　　
還看到一個比較神的nk做法

O（Nk）時間復雜度0ms過

只有一列的不用說吧，我說下兩列的

考慮每一行的狀態

0 空出這一行

1 選擇左邊空出右邊

2 選擇右邊空出左邊

3 選擇這一行兩個（不作為一個矩陣，而是左邊一列單獨一個矩陣，右邊單獨一個矩陣）

4 選擇這一行兩個（兩個一塊作為一個矩陣的一部分）

定義f[i,j,k]為當前處理到第i行，已經選了j個矩陣，當前行狀態為k的最大值（k為上面的0-4種狀態）

如果空出這一行，則j不需要變化，直接繼承上一行的各種狀態的最大值

f[i][j][0]=max(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]);

如果選擇左邊空出右邊，如果上一行的左邊沒有單獨地選擇成為矩陣的話（即選擇1或3），則j需要包含新選擇成為的矩陣（即這一行的左邊的這個矩陣）,

如果上一行為同時選擇兩列的為一個矩陣的狀態，則只選擇單獨的左邊是不能包含進去上一行的矩陣的，所以也應j-1(t1為這一行左邊的值)

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])+t1;

右邊同理(t2為這一行右邊的值)

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])+t2;

選擇兩個分別單獨作為矩陣，類似只選擇左邊或右邊，不過是單獨選左邊和右邊合并了下

f[i][j][3]=max(f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j][3])+t1+t2;

if(j>=2) f[i][j][3]=max(f[i][j][3],f[i-1][j-2][4]+t1+t2);

選擇兩個作為一個矩陣，則上一行除了可以接上的，都得j-1

f[i][j][4]=max(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j-1][3],f[i-1][j][4])+t1+t2;