1717.cpp

PKU1717-多米诺.DP实现,具体的转移方程可以看代码.

/*
PKU1717
2009-5-9 19:58:00
DP 
*/
#include <stdio.h>
#include <string.h>
#define MAXVALUE 6001
#define MAXSIZE 1001
#define oo 9999999
int n;
int dominos[MAXSIZE];
int dp1[MAXVALUE * 2 + 1], dp2[MAXVALUE * 2 + 1];

int solve(int sum) {
	int i, j, k, max, min, x, y, ans;
	memset(dp1, -1, sizeof(dp1));
	//memset(dp2, -1, sizeof(dp2));
	dp1[MAXVALUE + sum] = 0;	
	memcpy(dp2, dp1, sizeof(dp1));
	max = min = MAXVALUE + sum;
	x = y = MAXVALUE + sum;
	for(i = 0; i < n; ++i) {
		for(j = max; j >= min; --j) {
			if(dp1[j] != -1) {
				if(dp2[j - 2 * dominos[i]] == -1 || (dp2[j - 2*dominos[i]] > dp1[j] + 1)) {
					dp2[j - 2 * dominos[i]] = dp2[j] + 1;
					if(j - 2 * dominos[i] > x) x = j - 2 * dominos[i];
     				if(j - 2 * dominos[i] < y) y = j - 2 * dominos[i];
				}
			}
		}
		memcpy(dp1, dp2, sizeof(dp2));
		min = y;
		max = x;
	}
	i = 0;
	ans = oo;
	while(1) {
		if(dp1[MAXVALUE + i] != -1) ans = dp1[MAXVALUE + i];
		if(dp1[MAXVALUE - i] != -1 && ans > dp1[MAXVALUE - i]) {
			ans = dp1[MAXVALUE - i];
		}
		if(ans != oo) break;
		++i;
	}
	printf("%d\n", ans);
}

int main() {
	int i, j, k, sum;
	while(scanf("%d", &n) != EOF) {
		sum = 0;
		for(i = 0; i < n; ++i) {
			scanf("%d%d", &j, &k);
			dominos[i] = j - k;
			sum += dominos[i];
		}
		solve(sum);
	}
	return 0;
}