UVA_10123
以下斜体部分是我第一次写的解题报告，但后来越来越觉得我实现的程序和我的想法并不怎么挂钩，于是就越发怀疑程序里那个剪枝的正确性了。
再后来看了UVA的论坛之后，发现上面有人提到用记忆化搜索去解，我这时再一看N只有20，完全可以用状态压缩+记忆化搜索来做，只是当时没有想到，其中一部分原因也是觉得LRJ放在了回溯这章里面，就压根没向着dp的方向去考虑，一直在想怎么剪枝去了，便也凑巧，居然诞生了下面的我现在也不知道正确与否的回溯做法。以后千万不要局限于已知的这题的归类，换个思路也许就能海阔天空了。
如果各位兄台谁有兴趣证明出了或者推翻了下面这个回溯的程序，还望能和小弟分享一下。当然，这个回溯程序在UVA上是能AC的，而且跑得很快，但我后来总觉得这个程序的剪枝有问题。
下面还是说一下dp的思路吧。由于N不大，2的20次方也就10^6左右，因此可以把所有木块的状态用2进制表示出来，于是可以用f[i]表示是否可以达到木块的状态为i的这种状态。接下来我们既可以一个一个地向上放，也可以一个一个地向下拿，只要看最后起始状态的f[st]是否为1即可。
“首先，我们如果考虑怎么拿的话会比较麻烦，不如我们反过来考虑怎么放，如果每个时刻放的都能平衡，那么最后就能得出一个可行解。
“但是如果直接回溯的话会超时，我们不妨慢慢来优化算法。
“第一，最好把坐标先乘2化成整数，这样就避免了浮点数误差。
“第二，我们在放的时候，一个贪心思路就是先把两个支点中间的木块放上，比较容易证明这样只会增加后续木板的稳定程度。
“第三，我们应该把其余的木块按力矩大小降序排序，支点是离它最近的那个支点，先选力矩小的，这样一定程度上减少了木板弄翻的可能。
“第四，上面的按力矩排序还带来了额外的好处，我们不妨用两个数组分别存左边和右边的待放的木块。我们先考虑右边的，假设我们现在放了一个木块上去，结果发现后面无论怎么放木板都会右翻，显然就不用再尝试这个木块右边的木块了，因为必然也会右翻。同样，对于左边的木块，假设我们现在放了一个木块上去，结果发现后面无论怎么放木板都会左翻，显然就不用再尝试这个木块左边的木块了，因为必然也会左翻。当然，如果后续可能左翻也可能右翻的话就要继续尝试剩余的木块。
“考虑完上面几点之后就可以AC了。”
//深搜剪枝，回溯 #include#include #include #define MAXD 30 int L, N, W, s[MAXD], r1[MAXD], r2[MAXD], N1, N2, x[MAXD], w[MAXD], vis[MAXD]; int cmp(const void *_p, const void *_q) { int *p = (int *)_p; int *q = (int *)_q; int x1 , x2; if(x[*p] < 0) x1 = (-3 - x[*p]) * w[*p]; else x1 = (x[*p] - 3) * w[*p]; if(x[*q] < 0) x2 = (-3 - x[*q]) * w[*q]; else x2 = (x[*q] - 3) * w[*q]; return x1 - x2; } void init() { int i; for(i = 0; i < N; i ++) { scanf("%d%d", &x[i], &w[i]); x[i] *= 2; } } int dfs(int left, int right, int num) { int i, j, k, t, flag, mleft, mright, tleft = 1, tright = 1; if(num == N) return 2; for(i = 0; i < N1; i ++) { k = r1[i]; if(!vis[k]) { vis[k] = 1; mleft = left + (x[k] + 3) * w[k], mright = right + (3 - x[k]) * w[k]; s[num] = k; if(mleft >= 0) tleft = 0; if(mleft >= 0 && mright >= 0) { flag = dfs(mleft, mright, num + 1); if(flag == 2) return 2; if(flag == -1) break; tleft = 0; } vis[k] = 0; } } for(i = 0; i < N2; i ++) { k = r2[i]; if(!vis[k]) { vis[k] = 1; mleft = left + (x[k] + 3) * w[k], mright = right + (3 - x[k]) * w[k]; s[num] = k; if(mright >= 0) tright = 0; if(mleft >= 0 && mright >= 0) { flag = dfs(mleft, mright, num + 1); if(flag == 2) return 2; if(flag == 1) break; tright = 0; } vis[k] = 0; } } return tright - tleft; } void solve() { int i, j, k, left, right, num; memset(vis, 0, sizeof(vis)); num = 0; left = right = 3 * W; for(i = 0; i < N; i ++) if(x[i] >= -3 && x[i] <= 3) { s[num ++] = i; vis[i] = 1; left = left + (x[i] + 3) * w[i], right = right + (3 - x[i]) * w[i]; } N1 = N2 = 0; for(i = 0; i < N; i ++) if(!vis[i]) { if(x[i] < 0) r1[N1 ++] = i; else r2[N2 ++] = i; } qsort(r1, N1, sizeof(r1[0]), cmp); qsort(r2, N2, sizeof(r2[0]), cmp); if(dfs(left, right, num) != 2) printf("Impossible\n"); else { for(i = N - 1; i >= 0; i --) printf("%d %d\n", x[s[i]] / 2, w[s[i]]); } } int main() { int t = 0; for(;;) { scanf("%d%d%d", &L, &W, &N); if(!L) break; init(); printf("Case %d:\n", ++ t); solve(); } return 0; }
//状态压缩+记忆化搜索 #include#include #define MAXD 1100000 #define MAXN 25 int N, L, W, x[MAXN], w[MAXN]; int f[MAXD], left[MAXD], right[MAXD]; void init() { int i; for(i = 0; i < N; i ++) { scanf("%d%d", &x[i], &w[i]); x[i] *= 2; } } int dp(int st) { int i, k, mleft, mright; if(f[st] != -1) return f[st]; if(st == 0) return f[st] = 1; for(i = 0; i < N; i ++) if((1 << i) & st) { mleft = left[st] + (x[i] + 3) * w[i]; mright = right[st] + (3 - x[i]) * w[i]; if(mleft >= 0 && mright >= 0) { k = st ^ (1 << i); left[k] = mleft, right[k] = mright; if(dp(k)) { printf("%d %d\n", x[i] / 2, w[i]); return f[st] = 1; } } } return f[st] = 0; } void solve() { int i, st; memset(f, -1, sizeof(f)); st = (1 << N) - 1; left[st] = W * 3, right[st] = W * 3; if(!dp(st)) printf("Impossible\n"); } int main() { int t = 0; for(;;) { scanf("%d%d%d", &L, &W, &N); if(!L) break; init(); printf("Case %d:\n", ++ t); solve(); } return 0; }