Posts Tagged ‘状态压缩’

POJ 2411 Mondriaan’s Dream

Posted in PKU OJ on 四月 8th, 2010 by 纳米 – Be the first to comment

2009-12-02，AC

解题报告：
这是一道状态压缩DP。首先对每一行设计状态，对于某个位置，有空和非空两种情况。什么情况下进行状态转移呢?
(1) (x, y)为空，(x-1, y)不为空，表示该(x, y)为一个竖着的方块的上面一格；
(2) (x, y)不为空，(x-1, y)为空，表示该(x, y)为一个竖着的方块的下面一格；
(3) (x, y)、(x-1, y)均不为空，并且一行中有一段连续的、数量为偶数的这样的格子，表示这一段连续的格子为横着的方块。
我们用0表示空，1表示非空，每行不超过11个格子，于是我们可以进行二进制编码。为了提高速度，可以预先处理某个状态A可以从哪些状态转移而来。
还有一个优化，就是h*w为奇数答案显然为0。

当然，可以打表-.-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#include <stdio.h>
#include <string.h>
 
const int pow[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
const int maxn = 11, maxpow = 2049;
 
int n, m;
int match[maxpow][maxpow], size[maxpow] = {0};
long long dp[2][maxpow];
 
bool check1(int x, int y) {
	int c = 0;
	for (int i = 0; i < m; ++i) {
		if (!(x & 1) && !(y & 1))
			return false;
		if (x & 1 ^ y & 1 && c & 1)
			return false;
		if (x & 1 && y & 1)
			++c;
		x >>= 1;
		y >>= 1;
	}
	if (c & 1)
		return false;
	else
		return true;
}
 
bool check2(int x) {
	int c = 0;
	while (x > 0) {
		if (x & 1)
			++c;
		else if (c & 1)
			return false;
		x >>= 1;
	}
	return !(c & 1);
}
 
int init() {
	memset(size, 0, sizeof(size));
	for (int i = 0; i < pow[m]; ++i)
		for (int j = 0; j < pow[m]; ++j)
			if (check1(i, j))
				match[i][size[i]++] = j;
	return 0;
}
 
long long work() {
	int pm = pow[m];
	memset(dp[1], 0, sizeof(dp[1]));
	for (int i = 0; i < pm; ++i)
		if (check2(i))
			dp[1][i] = 1;
	for (int i = 2; i <= n; ++i) {
		int now = i & 1;
		int pre = 1 - now;
		memset(dp[now], 0, sizeof(dp[now]));
		for (int j = 0; j < pm; ++j)
			for (int k = 0; k < size[j]; ++k)
				dp[now][j] += dp[pre][match[j][k]];
	}
	int now = n & 1;
	int pre = 1 - now, pm1 = pm - 1;
	dp[now][pm1] = 0;
	for (int k = 0; k < size[pm1]; ++k)
		dp[now][pm1] += dp[pre][match[pm1][k]];
	return dp[n & 1][pm - 1];
}
 
int main() {
	while (1) {
		scanf("%d%d", &n, &m);
		if (n == 0 || m == 0)
			break;
		if (n * m & 1) {
			printf("0\n");
		} else {
			if (n < m) {
				int t = n;
				n = m;
				m = t;
			}
			init();
			printf("%I64d\n", work());
		}
	}
	return 0;
}

POJ 2288 Islands and Bridges

Posted in PKU OJ on 四月 8th, 2010 by 纳米 – Be the first to comment

2009-12-02，AC

解题报告：
哈密顿回路是NPC问题。但是由于n<=13，可以采取状态压缩DP解决。
每个状态按照题目给出要求转移就可以了。注意要使用long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
const int maxn = 13, maxm = 157, maxpow = 8193;
const int pow[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192};
 
int n, m, edge[maxn][maxn + 2], list[maxm][2];
long long data[maxn], dp[maxpow][maxn][maxn], dp_c[maxpow][maxn][maxn];
bool exist[maxn][maxn];
struct __ZT{
	int s, size;
	bool exist[maxn];
} ZT[maxpow], zt[maxpow];
long long answer, answer_c;
 
int init() {
	for (int i = 1; i < pow[maxn]; ++i) {
		ZT[i].s = i;
		ZT[i].size = 0;
		memset(ZT[i].exist, 0, maxn);
		for (int j = 0; j < maxn; ++j)
			if (pow[j] & i) {
				ZT[i].exist[j] = 1;
				++ZT[i].size;
			}
	}
	return 0;
}
 
int input() {
	memset(exist, 0, sizeof(exist));
	memset(edge, 0, sizeof(edge));
 
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
		scanf("%I64d", &data[i]);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (u != v) {
			--u;--v;
			exist[u][v] = exist[v][u] = 1;
		}
	}
	int j = 0;
	for (int u = 0; u < n; ++u)
		for (int v = 0; v < n; ++v)
			if (exist[u][v]) {
				edge[u][++edge[u][0]] = v;
				list[j][0] = u;
				list[j][1] = v;
				++j;
			}
	m = j;
	return 0;
}
 
int comp(__ZT *x, __ZT *y) {
	return x->size - y->size;
}
 
int work() {
	if (n == 1) {
		answer = data[0];
		answer_c = 1;
	} else if (n == 2) {
		if (exist[0][1]) {
			answer = data[0] + data[1] + data[0] * data[1];
			answer_c = 1;
		} else {
			answer = answer_c = 0;
		}
	} else {
		memcpy(zt, ZT, sizeof(__ZT) * pow[n]);
		qsort(&zt[1], pow[n] - 1, sizeof(__ZT), (int(*) (const void*, const void*)) comp);
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < m; ++i) {
			int u = list[i][0], v = list[i][1];
			int A = pow[u] + pow[v];
			dp[A][u][v] = data[u] * data[v];
			dp_c[A][u][v] = 1;
		}
		for (int i = (n * n + n) / 2 + 1; i < pow[n]; ++i) {
			int A = zt[i].s;
			for (int j = 0; j < m; ++j) {
				int u = list[j][0], v = list[j][1];
				if (zt[i].exist[u] && zt[i].exist[v]) {
					int B = A - pow[v];
					for (int k = 1, w = edge[u][1]; k <= edge[u][0]; w = edge[u][++k])
						if (pow[w] & B && dp[B][w][u]) {
							long long x = dp[B][w][u] + (exist[w][v] ? data[u] * data[v] * data[w] : 0);
							if (x > dp[A][u][v]) {
								dp[A][u][v] = x;
								dp_c[A][u][v] = dp_c[B][w][u];
							} else if (x == dp[A][u][v]) {
								dp_c[A][u][v] += dp_c[B][w][u];
							}
						}
					if (dp[A][u][v])
						dp[A][u][v] += data[u] * data[v];
				}
			}
		}
		answer = 0;
		int A = pow[n] - 1;
		for (int i = 0; i < m; ++i) {
			int u = list[i][0], v = list[i][1];
			if (dp[A][u][v] > answer) {
				answer = dp[A][u][v];
				answer_c = dp_c[A][u][v];
			} else if (dp[A][u][v] == answer) {
				answer_c += dp_c[A][u][v];
			}
		}
		if (answer) {
			for (int i = 0; i < n; ++i)
				answer += data[i];
			answer_c >>= 1;
		} else {
			answer = answer_c = 0;
		}
	}
	return 0;
}
 
int output() {
	printf("%I64d %I64d\n", answer, answer_c);
	return 0;
}
 
int main() {
	init();
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		input();
		work();
		output();
	}
	return 0;
}