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.
2023年4月18日 17:22
Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest. edpost is an edpost.in initiative of professional writers who have banded together to provide devoted news coverage of current events in India.
2024年1月05日 20:19
Pavzi.com is a startup by passionate webmasters and bloggers who have a passion for providing engaging content that is accurate, interesting, and worthy to read. pavzi.com We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news. We provide you with the finest web content on every topic possible with the help of the editorial and content team.