BZOJ1084 [SCOI2005]最大子矩阵【DP】
【题解】
当$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; }