UVA1377

读完题意就知道是一个暴力乱搞题，但是苦于水平有限，只能赛后补

UVA1377

题意：n个长度值，需要提供一把刻度尺，尺子上的刻度越少越好，尺子越短越好，要求是：必须有0刻度，n个长度值可以直接测量

注意hint的提示：最多就是7个！

我自己想的是二进制枚举：

把0这个长度值放入n个长度值中

任意一个状态用一个整数表示，然后去判断，选择覆盖了所有长度值得方案

因为i值是从小到大的，所以只要对n个长度值排序去重，就可以保证满足刻度少且长度短的限制条件

这种方法都是错的！因为有可能出现这种数据11 21 31 41 51 61 71 81

然后答案应该是0 10 21 41 61 81，即可以用大的和差值去构造小的

同理，也可以用加法构造

意味着，可以出现这n个长度值之外的数

for(int i=0;i<(1<<n);i++)
	if (ok(i)){
		getans(i);
		break;
	}

暴力bfs或者dfs都可以，提供两种不同的姿势

bfs来源：http://blog.csdn.net/accelerator_/article/details/18312437

bfs想法：每添加一条边，就和现有的所有状态来判断，是不是因为这条边的加入，使得可以创造出n个长度中的某几个，然后状态压缩放进去，新状态继续放入队列。当队列中有元素满足时候，记得最优值；当队列为空的时候，就可以退出

#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

int N,n,id[maxnum],d[25],cas=0,Max,vis[maxnum<<1];
set<int> ans;
struct S{
	int state;
	set<int> ans;
}p;

void init(){
	int D;
	n=0;
	ans.clear();
	memset(id,0,sizeof(id));
	memset(vis,0,sizeof(vis));
	for(int i=0;i<N;i++){
		scanf("%d",&D);
		if (!id[D]){
			d[n++]=D;
			id[D]=1;
		}
	}
	sort(d,d+n);
	Max=d[n-1];
	memset(id,-1,sizeof(id));
	for(int i=0;i<n;i++) id[d[i]]=i;
	//for(int i=0;i<n;i++) printf("%d%c",id[d[i]],i==n-1?'\n':' ');
	//id[d[i]是给每条边编号，方便二进制枚举时候的一一对应 
	//for(int i=0;i<n;i++) printf("%d%c",d[i],i==n-1?'\n':' ');
	//这个值就是序号值 
}

void BFS(){
	queue<S> Q;
	p.ans.clear();
	p.ans.insert(0);
	p.state=0;
	//初始化节点 
	Q.push(p);
	while(!Q.empty()){
		p=Q.front();
		Q.pop();
		if (p.state==(1<<n)-1){
			//判断是不是达到终点了，所有的边都出现过 
			if (ans.size()==0) ans=p.ans;
			else{
				if (ans.size()<p.ans.size()) return;
				else if (ans.size()>p.ans.size()) ans=p.ans;
				else if (*ans.rbegin()>*p.ans.rbegin()) ans=p.ans;
			}
			//现有解和当前最优解取较优解 
		}
		if (p.ans.size()==7) continue;
		//达到最大数量的剪枝，不需要继续计算
		for(int i=0;i<n;i++){
			if ((p.state)&(1<<i)) continue;
			//如果当前这条边出现过，就没有意义 下面用减法或者加法来得到d[i]的长度
			for(set<int>::iterator it=p.ans.begin();it!=p.ans.end();it++){
				if (*it>d[i]){//如果可以利用减法，往前看算出长度 
					S q=p;
					int sum=*it-d[i];
					for(set<int>::iterator it2=q.ans.begin();it2!=q.ans.end();it2++){
						int nu=abs(*it2-sum);
						if (id[nu]==-1) continue;
						q.state=(q.state|(1<<id[nu]));
					}
					q.ans.insert(sum);
					if (!vis[q.state]){
						Q.push(q);
						vis[q.state]=1;
					}
				}
				if (*it+d[i]<=Max){//如果可以利用加法，往后看算出长度 
					S q=p;
					int sum=*it+d[i];
					for(set<int>::iterator it2=q.ans.begin();it2!=q.ans.end();it2++){
						int nu=abs(*it2-sum);
						if (id[nu]==-1) continue;
						q.state=(q.state|(1<<id[nu]));
					}
					q.ans.insert(sum);
					if (!vis[q.state]){
						Q.push(q);
						vis[q.state]=1;
					}
				}
			}
		}
	}
}

void solve(){
	BFS();
	int bo=0;
	printf("Case %d:\n%d\n",++cas,ans.size());
	for(set<int>::iterator it=ans.begin();it!=ans.end();it++){
		if (bo++) printf(" ");
		printf("%d",*it);
	}
	puts("");
}

int main(){
	//input;
	while(scanf("%d",&N)!=EOF){
		if (!N) break;
		init();
		solve();
	}
	return 0;
}

dfs的方法是另外一位聚聚，弱还没太懂，上链接吧

http://www.cnblogs.com/GeniusYang/p/5460642.html

解释：

学习了这些巨巨的代码，非常感谢