LA 4794 Sharing Chocolate (搜索)

　　搞了一个晚上。。一道搜索可行解的题，开始的时候理解错了，以为可以dp直接搞掂。不过仔细想了一下，发现就算是理解错题意，dp起来也是很麻烦的。。。- -

　　最后瞄了一下题解，调了一晚，搞掂括号放错位置的问题以后就过了。。囧。

AC code：

View Code

 1 #define REP(i, n) for (int i = 0; i < (n); i++)
 2 
 3 int sum[N], sz[20];
 4 bool vis[N][M];
 5 
 6 void input(int n) {
 7     REP(i, n) cin >> sz[i];
 8     REP(i, 1 << n) {
 9         sum[i] = 0;
10         REP(j, n) if (i & (1 << j)) sum[i] += sz[j];
11         REP(j, M) vis[i][j] = false;
12     }
13 }
14 
15 inline int bitCount(int x) {
16     int cnt = 0;
17     while (x) cnt += x & 1, x >>= 1;
18     return cnt;
19 }
20 
21 bool dfs(int st, int x) {
22     if (bitCount(st) == 1 && sum[st] % x == 0) {
23         return true;
24     }
25     if (vis[st][x]) return false;
26     int y = sum[st] / x;
27     for (int t = (st - 1) & st; t; t = (t - 1) & st) {
28         int nt = st ^ t;
29         if (!(sum[t] % x) && dfs(t, min(x, sum[t] / x)) && dfs(nt, min(x, sum[nt] / x))) return true;
30         if (!(sum[t] % y) && dfs(t, min(y, sum[t] / y)) && dfs(nt, min(y, sum[nt] / y))) return true;
31     }
32     vis[st][x] = true;
33     return false;
34 }
35 
36 int main() {
37     int x, y, n, cas = 1;
38     while (cin >> n && n) {
39         cin >> x >> y;
40         input(n);
41         printf("Case %d: ", cas++);
42         if (sum[(1 << n) - 1] == x * y && dfs((1 << n) - 1, min(x, y))) puts("Yes");
43         else puts("No");
44     }
45     return 0;
46 }

——written by Lyon