uvalive 3667(dfs)

题意：有n个长度需要测量，有一个刻度尺上有m个刻度，现在要所有的长度可以在刻度尺上直接测量出来，问在保证尺子长度尽量短的情况下m最小是多少，并输出这m个刻度。

题解：因为题目中提到m最大为7，可以暴力，首先为了让保证尺子长度最短，所以最后一个刻度一定是最大长度，把d数组排序去重，然后m * (m + 1) / 2 = n 中m是可能的最小的m，所以从这个m开始拿去暴力求解，然后枚举出一个值(vis[number] = 1)后，把剩下d中可以通过刚才枚举的值直接测量的都剔除掉(vis[number] = 1)，继续递归，刻度数量达到当前m，如果所有d都可以直接测量(vis[number] == 1)，返回true。

#include <stdio.h>
#include <queue>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 55;
int n, d[N], res[N], pos[1000005], len, vis[N];

bool dfs(int cnt) {
	if (cnt == len) {
		for (int i = 1; i <= n - 1; i++)
			if (!vis[i])
				return false;
		return true;
	}
	for (int i = 1; i <= cnt - 1; i++)
		for (int j = 1; j <= n - 1; j++) {
			if (!vis[j]) {
				int temp = res[i] + d[j];
				if (temp >= d[n] || temp <= res[cnt - 1])
					continue;
				res[cnt] = temp;
				queue<int> q;
				for (int k = 1; k <= cnt - 1; k++) {
					temp = res[cnt] - res[k];
					if (pos[temp] && !vis[pos[temp]]) {
						vis[pos[temp]] = 1;
						q.push(pos[temp]);
					}
				}
				temp = d[n] - res[cnt];
				if (pos[temp] && !vis[pos[temp]]) {
					vis[pos[temp]] = 1;
					q.push(pos[temp]);
				}
				if (dfs(cnt + 1))
					return true;
				while (!q.empty()) {
					vis[q.front()] = 0;
					q.pop();
				}
			}
		}
	return false;
}

int main() {
	int cas = 1;
	while (scanf("%d", &n) == 1 && n) {
		memset(vis, 0, sizeof(vis));
		memset(pos, 0, sizeof(pos));
		for (int i = 1; i <= n; i++)
			scanf("%d", &d[i]);
		sort(d + 1, d + 1 + n);
		n = unique(d + 1, d + 1 + n) - d - 1;
		for (int i = 1; i <= n; i++)
			pos[d[i]] = i;
		len = sqrt(2 * n) - 1;
		res[1] = 0;
		while (!dfs(2))
			len++;
		res[len] = d[n];
		printf("Case %d:\n", cas++);
		printf("%d\n", len);
		for (int i = 1; i <= len; i++)
			printf("%d ", res[i]);
		printf("\n");
	}
	return 0;
}

uvalive 3667(dfs)

原文：http://blog.csdn.net/hyczms/article/details/44659609