首页 > 代码库 > UVA - 10558A Brief Gerrymander(递推)

UVA - 10558A Brief Gerrymander(递推)

题目大意:UVA - 10558A Brief Gerrymander(递推)


题目大意:给定一个100 * 100 的矩形,现在要求将这个区域划分,竖着的线已经给你划分好了,现在要求你在这个区域内再添加A个横着的线,1 100 这两条是一定要的,问怎样选择横着的线,能够使得选举区间最多。选举区间的条件:内部没有横竖线,并且有一个点在区间内部。注意:边界上的点也是算在内的,但是要防止重复计算到选区内。


解题思路:这题题意都不是那么好理解了,然后写起来复杂度也是很大的。参考了别人的题解:首先:dp[i][j]代表第i根横线的序号是j的时候,有多少个选区。S【i】【j】代表:第i根横线到第j根横线之间在已知竖线的情况下有多少个选区。注意这里因为要算边界的点,所以i到j是左闭右开【i,j)(包括i这线上的点,但是不包括j这条横线上的点)。dp【【i】【j】 =Max ( dp【i - 1】【k】 + s【k】【j】));

所以先要预处理出S【i】【j】:处理的时候也需要找个策略不然复杂度也是很高。用G【i】【j】【k】代表第i条横线到第j条横线和第i - 1竖线和第i条竖线是否是选取区。G【i】【j】【k】 |= G[i][j - 1][k];

G[i][j][k] |= t【j】【k】(第j - 1条直线上是否有点在K-1和k竖线之间,注意这里竖线的边界点也要计算,并且要防止重复。同理:【K -1 ,K)。


代码:

#include <cstdio>
#include <cstring>

const int N = 105;

int n, m;
int s[N][N];
int t[N][N];
int dp[N][N];
int p[N][N];
int street[N];
int G[N][N][N];
int path[N][N];

int Max (const int a, const int b) { return a > b ? a: b; }

void init () {

	memset (t, 0, sizeof (t));
	for (int i = 1; i <= 100; i++) {	
		for (int j = 1; j < m; j++) {	
			int k;
			for (k = street[j - 1]; k < street[j]; k++)
				if (p[i - 1][k])
					break;
			if (k != street[j])
				t[i][j] = 1;
		}
	}

	memset (G, 0, sizeof (G));
	memset (s, 0, sizeof (s));
	for (int i = 1; i < 100; i++) {
		for (int j = 1; j + i <= 100; j++) {
		
			for (int k = 1; k < m; k++)
				G[j][j + i][k] |= G[j][j + i - 1][k];
			
			for (int k = 1; k < m; k++)
				G[j][j + i][k] |= t[j + i][k];
			for (int k = 1; k < m; k++)
				if (G[j][j + i][k])
					s[j][j + i]++;
		}
	}

}

void printf_ans (int A, int j) {

	if (path[A][j] == -1)
		return;
	printf_ans (A - 1, path[A][j]);
	printf (" %d", path[A][j]);					
}

int main () {

	int x, y, A;
	while (scanf ("%d", &n) && n != -1) {

		memset (p, 0, sizeof (p));
		for (int i = 0; i < n; i++) {

			scanf ("%d%d", &x, &y);
			p[y][x] = 1;
		}
		scanf ("%d", &m);
		for (int i = 0; i < m; i++)
			scanf ("%d", &street[i]);
		scanf ("%d", &A);

		init ();

		dp[1][1] = 0;
		path[1][1] = -1;
		for (int i = 2; i <= A; i++) {
			for (int j = i; j <= 100; j++) {

				dp[i][j] = 0;
				if (i == 2) {
					dp[i][j] = Max (dp[i][j] , dp[1][1] + s[1][j]);
					path[i][j] = 1;
				} else {

					for (int k = 2; k < j; k++) { 
						if (dp[i - 1][k] + s[k][j] >= dp[i][j])
							path[i][j] = k;
						dp[i][j] = Max (dp[i][j] , dp[i - 1][k] + s[k][j]);
					}
				}
			}
		}
		
//		printf ("%d\n", t[50][1]);
		printf ("%d", A);
		printf_ans(A, 100);
		printf (" 100\n");
				
	}	
	return 0;
}