Posts Tagged ‘多次搜索’

POJ 1069 The Bermuda Triangle

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

2010-05-18，阅读题目，Code，WA，AC
某年GDKOI也出过这一题，所以去年写过一次这题，然后有一个点TLE的。今天重写，没有TLE了。

解题报告：
首先要做的，就是对各个三角形进行编号，方便程序设计。这个爱怎么写就怎么写。然后主过程就是硬搜了，主要优化如下：
1. 如果小三角形边长不能组成大三角形（六边形的1/6，下同），则直接输出NO
2. 如果同种小三角形能直接组成大三角形，则直接输出YES
3. 当前剩余的面积无法用小三角形组合而成，剪枝
4. 搜小三角形的时候，从大到小搜
5. 先搜1/6，然后搜1/3、1/2，再搜索整个大三角形。为什么呢？如果用小三角形能组成1/6的六边形，则整个六边形都显然可以用小三角形组合而成，1/3、1/2同理。

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
const int maxn = 53, maxm = 11, maxcb = 3755;
int n, m, nw, data[maxm], pow[maxn], pw[maxn][2];
bool cf[maxn][maxn], cb[maxcb];
 
int input() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
		scanf("%d", &data[i]);
	return 0;
}
 
int comp(int *x, int *y) {
	return *y - *x;
}
 
int work_init() {
	for (int i = 0; i <= n; ++i)
		pow[i] = i * i;
	qsort(&data[1], m, sizeof(int), (int(*) (const void*, const void*)) comp);
	int m0 = 0, pt = pow[n] * 6;
	data[0] = 0;
	for (int i = 1; i <= m; ++i)
		if (data[i] <= n && data[i] != data[i-1])
			data[++m0] = data[i];
	m = m0;
	memset(cb, 0, sizeof(cb));
	cb[0] = 1;
	for (int i = 1; i <= m; ++i)
		for (int j = pow[data[i]], jj = 0; j <= pt; ++j, ++jj)
			cb[j] = cb[jj] || cb[j];
	nw = n & 1;
	return 0;
}
 
bool check_line() {
	bool dp[maxn];
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	for (int i = 1; i <= m; ++i)
		for (int j = data[i]; j <= n; ++j)
			dp[j] = dp[j-data[i]] || dp[j];
	return dp[n];
}
 
bool can_fill(int x, int y, int t) {
	if (((x + y) & 1) == nw) {
		x += t-1, y += t-1;
		for (int i = 0; i < t; ++i)
			for (int j = -i; j <= i; ++j)
				if (!cf[x-i][y+j])
					return false;
	} else {
		for (int i = 0; i < t; ++i)
			for (int j = -i; j <= i; ++j)
				if (!cf[x+i][y+j])
					return false;
	}
	return true;
}
 
void fill(int x, int y, int t, bool w) {
	if (((x + y) & 1) == nw) {
		for (int i = 0; i < t; ++i)
			for (int j = -i; j <= i; ++j)
				cf[x+t-i-1][y+t+j-1] = w;
	} else {
		for (int i = 0; i < t; ++i)
			for (int j = -i; j <= i; ++j)
				cf[x+i][y+j] = w;
	}
}
 
bool search(int x, int y, int s) {
	bool res = false;
	int x0 = y < pw[x][1] ? x : x + 1;
	int y0 = y < pw[x][1] ? y + 1 : pw[x+1][0];
	if (!s) {
		res = true;
	} else if (cf[x][y]) {
		for (int i = 1; i <= m && !res; ++i)
			if (can_fill(x, y, data[i]) && cb[s - pow[data[i]]]) {
				fill(x, y, data[i], 0);
				res = search(x0, y0, s - pow[data[i]]);
				fill(x, y, data[i], 1);
			}
	} else {
		res = search(x0, y0, s);
	}
	return res;
}
 
bool check_1() {
	memset(cf, 0, sizeof(cf));
	pw[0][0] = n + 1;
	pw[0][1] = n - 1;
	for (int i = 1; i <= n; ++i) {
		pw[i][0] = pw[i-1][0] - 1;
		pw[i][1] = pw[i-1][1] + 1;
		for (int j = pw[i][0]; j <= pw[i][1]; ++j)
			cf[i][j] = 1;
	}
	return search(1, n, pow[n]);
}
 
bool check_2() {
	memset(cf, 0, sizeof(cf));
	pw[0][0] = n + 1;
	pw[0][1] = n + n + n;
	for (int i = 1; i <= n; ++i) {
		pw[i][0] = pw[i-1][0] - 1;
		pw[i][1] = pw[i-1][1] - 1;
		for (int j = pw[i][0]; j <= pw[i][1]; ++j)
			cf[i][j] = 1;
	}
	return search(1, n, pow[n] * 2);
}
 
bool check_3() {
	memset(cf, 0, sizeof(cf));
	pw[0][0] = n + 1;
	pw[0][1] = n + n + n - 1;
	for (int i = 1; i <= n; ++i) {
		pw[i][0] = pw[i-1][0] - 1;
		pw[i][1] = pw[i-1][1] + 1;
		for (int j = pw[i][0]; j <= pw[i][1]; ++j)
			cf[i][j] = 1;
	}
	return search(1, n, pow[n] * 3);
}
 
bool check_6() {
	memset(cf, 0, sizeof(cf));
	pw[0][0] = n + 1;
	pw[0][1] = n + n + n - 1;
	for (int i = 1; i <= n + n; ++i) {
		if (i != n+1) {
			pw[i][0] = i <= n ? pw[i-1][0] - 1 : pw[i-1][0] + 1;
			pw[i][1] = i <= n ? pw[i-1][1] + 1 : pw[i-1][1] - 1;
		} else {
			pw[i][0] = pw[i-1][0];
			pw[i][1] = pw[i-1][1];
		}
		for (int j = pw[i][0]; j <= pw[i][1]; ++j)
			cf[i][j] = 1;
	}
	return search(1, n, pow[n] * 6);
}
 
bool work_check() {
	for (int i = 1; i <= m; ++i)
		if (n % data[i] == 0)
			return true;
	if (!check_line())
		return false;
	if (check_1() || check_2() || check_3() || check_6())
		return true;
	return false;
}
 
int main() {
	int testCases;
	scanf("%d", &testCases);
	while (testCases--) {
		input();
		work_init();
		if (work_check())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}