POJ 2547 - No Tipping

http://poj.org/problem?id=2547

概要

長さ L，重さ W の板がある．この板の中心を座標 0 とし，左方向が負，右方向が正とする． 板は -1.5, +1.5 の位置にある2つの支点によって支えられている．

板の上には重りが N 個乗っており，それぞれ座標 x[i]，重さ w[i] である．

板が倒れないように，1つずつ重りを取り除きたいので，その手順を答える． ただし，どう取り除いても途中で倒れてしまう場合は「Impossible」と答える．

板が倒れるのは，左側の支点を中心としたトルクが反時計回りの方向ときか，右側の支点を中心としたトルクが時計回りの方向のときである．

制約

解法

板の上にある重りの状態は高々 2^20 通りなので，メモりながら DFS する．

status を見ると 0MS 近くで通されているので，もっと高速な方法がありそう．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 struct package { int x, w; };
 5 int N, W;
 6 package ps[20];
 7 int ans[20];
 8 
 9 bool ok(unsigned s)
10 {
11   double left = 1.5 * W, right = -1.5 * W;
12   for (int i = 0; i < N; i++) {
13     if (s & (1<<i)) {
14       left += ps[i].w * (ps[i].x + 1.5);
15       right += ps[i].w * (ps[i].x - 1.5);
16     }
17   }
18   return left >= 0.0 && right <= 0.0;
19 }
20 
21 bool valid[1<<20];
22 int memo[1<<20];
23 
24 bool dfs(unsigned s, int n)
25 {
26   if (memo[s] != -1) {
27     return memo[s];
28   }
29   if (s == 0) {
30     return true;
31   } else {
32     for (int i = 0; i < N; i++) {
33       if (ans[i] == -1) {
34         const unsigned t = s & ~(1<<i);
35         ans[i] = n;
36         if (valid[t] && dfs(t, n+1)) {
37           return (memo[s] = true);
38         }
39         ans[i] = -1;
40       }
41     }
42     return (memo[s] = false);
43   }
44 }
45 
46 int main()
47 {
48   int L;
49   for (int Ti = 1; scanf("%d %d %d", &L, &W, &N) != EOF && L != 0; Ti++) {
50     printf("Case %d:\n", Ti);
51     for (int i = 0; i < N; i++) {
52       scanf("%d %d", &ps[i].x, &ps[i].w);
53       ans[i] = -1;
54     }
55 
56     for (unsigned s = 0; s < (1<<N); s++) {
57       valid[s] = ok(s);
58       memo[s] = -1;
59     }
60 
61     if (dfs((1<<N)-1, 0)) {
62       package qs[20];
63       for (int i = 0; i < N; i++) {
64         qs[ans[i]] = ps[i];
65       }
66       for (int i = 0; i < N; i++) {
67         printf("%d %d\n", qs[i].x, qs[i].w);
68       }
69     } else {
70       puts("Impossible");
71     }
72   }
73   return 0;
74 }
poj/2547.cc