uva 10123(暴力求解)

题意：给出了木板的长度和重量，以及木板上有几个木块，然后每个木块的位置和重量也给出了，问如果一个一个的把木块丛天平上取下来让天平能够保持平衡的取下木块的顺序是什么，如果不能保持平衡，输出impossible。

题解：如果一开始就考虑怎么取的话比较麻烦，但如果反过来一个一个的向天平上放木块看是否保持平衡就很好考虑了，先放位置在左边的木块，从力矩小的到力矩大的（剪枝），直到天平会倾斜就开始放右边的木块，这样轮换放木块直到全部放上去，如果放到最后一个木块且依旧可以平衡就输出放的序列。做法是可以先将左边和右边的木块分开储存，因为此题的天平有两个支点，如果一个支点在考虑的时候另一个支点是可以忽略的，所以可以根据位置计算力矩，然后排序，递归去放置木块，在判断是否平衡的时候，注意考虑木板自身重量的影响，根据木板的支点不同，重心不同的原理，木板所占力矩也不同，计算可得力矩差要大于自身重量的1.5倍时才会倾斜。还有如果放置的木块在-1.5到1.5范围内，可以增大平衡度，即如果支点在-1.5，-1.5右边的木块都会成为右力矩，支点在1.5同理。然后就没有然后了。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 25;

struct P {
	int pos, weight, flu;
}left[N], right[N], res[N];
int boardl, boardw, n, vis[N], flag, rn, ln;

int cmp(P a, P b) {
	return a.flu < b.flu;
}

bool judge(int a, int l, int r) {
	double wl, wr;
	wl = wr = 0;
	for (int i = 0; i < r; i++)
		wr += (right[i].pos + 1.5) * right[i].weight;
	for (int i = 0; i < l; i++)
		wl += (-left[i].pos - 1.5) * left[i].weight;
	if ((wl - wr) > boardw * 1.5)//木块重量对平衡也是有影响的
		return 0;
	wl = wr = 0;
	for (int i = 0; i < r; i++)
		wr += (right[i].pos - 1.5) * right[i].weight;
	for (int i = 0; i < l; i++)
		wl += (-left[i].pos + 1.5) * left[i].weight;
	if ((wr - wl) > boardw * 1.5)
		return 0;
	return 1;
}

void dfs(int l, int r, int num) {
	if (num == n) {
		flag = 1;
		for (int i = n - 1; i >= 0; i--)
			printf("%d %d\n", res[i].pos, res[i].weight);
		return;
	}
	for (int i = l; i < ln; i++)
		if (judge(1, i, r) && !flag) {
			res[num].pos = left[i].pos;
			res[num].weight = left[i].weight;
			dfs(i + 1, r, num + 1);
		}
		else
			break;
	for (int i = r; i < rn; i++)
		if (judge(2, l, i) && !flag) {
			res[num].pos = right[i].pos;
			res[num].weight = right[i].weight;
			dfs(l, i + 1, num + 1);
		}
		else
			break;
}

int main() {
	int t = 1, a, b;
	while (scanf("%d%d%d", &boardl, &boardw, &n) && boardl) {
		flag = ln = rn = 0;	
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &a, &b);
			if (a >= 0) {
				right[rn].pos = a;
				right[rn].weight = b;
				right[rn++].flu = (a - 1.5) * b;//右边木块放置支点在右，距离减小1.5，下面同理
			}
			if (a < 0) {
				left[ln].pos = a;
				left[ln].weight = b;
				left[ln++].flu = (-a - 1.5) * b;
			}
		}
		sort(right, right + rn, cmp);//根据力矩排序
		sort(left, left + ln, cmp);
		printf("Case %d:\n", t++);
		dfs(0, 0, 0);
		if (!flag)
			printf("Impossible\n");
	}
	return 0;
}