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; }
2022年12月23日 14:40
When we are traveling we need to find Restrooms, Bathrooms, or Public Toilets in the current location. Using Google Maps, Google Assistant, Alexa, iPhone Siri, and other location finder services helps you to get Nearest Public Toilets and Washrooms easily. rest room near me Here we have discussed various location finder services that help you find the nearest public toilets near your current location where you are standing.
2023年2月03日 18:28
Are you getting yourself a new WiFi router, then you might be happy because now you are able to set up your best WiFi names to your liking which is a funny act but a please to do indeed. WiFi Names Well as you already know that the reason why people be objective about finding the best WiFi names for their new connections or routers is that they want some cool or funny names that make them feel nice and at the same time when your friends, family.