BZOJ1084 [SCOI2005]最大子矩阵【DP】

tonyfang posted @ 2016年8月17日 22:04 in BZOJ with tags C++ OI , 589 阅读






# 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;
rest room near me 说:
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.

WiFi Names 说:
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.

登录 *

loading captcha image...
or Ctrl+Enter