给你一系列的长度。你要制作一个有m个刻度的尺子，使得任意一个长度都能以某两个刻度之间的距离表示
要求m尽量小的前提下尺子长度尽量小。你可以认为刻度数不超过7
首先要想明白的一点，尺子长度就为这n个长度中的最大值。以这个值为长度的尺子一定能满足m尽量小。
然后我们如何去搜索呢？我们的刻度是任意的，但可以跟给定长度建立关系。我们枚举一个当前还不能表示的长度，然后枚举这个长度是由哪个已有刻度和新刻度共同产生的。这样的做法是显然能得到解的。还有一个重要问题，如何判重呢？我们只要判断当前状态能表示哪些刻度就有了——即表示的给定长度都相同的两种状态视为同一种状态。其中的原因可以这么想。因为枚举刻度的时候我们确定了左端点和右端点，即0和尺子的最大刻度。
然后这样对广搜判重的时候就有两种情况
1.当前得到的状态消耗刻度数比相同状态的所用刻度数多
这种情况不必多说，说明当前的刻度划分方式是不明智的一种，显然应该舍弃之。
2.当前得到的状态消耗刻度数和相同状态的所有刻度数一样多
因为左右端点确定，若他们表示的状态都相同，要么这两个尺子相同，要么这二者之间就类似是对称的。即在搜索中是可以类似进行操作的
来的渣比我讨论吧。。。参考别人才写的
#include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<queue> using namespace std; const int maxm=58; const int maxn=1000008; int a[maxm]; int b[maxm]; int idx; set<int> ans; int shit[maxn]; bool vis[maxn<<5]; struct fuck{ int state; set<int> ans; }f; void bfs() { queue<fuck> q; f.ans.clear();f.ans.insert(0);f.state=0; q.push(f); int i; while(!q.empty()) { f=q.front();q.pop(); // printf("%d ",f.state); if(f.state==(1<<idx)-1) { if(ans.size()==0) ans=f.ans; else { if(ans.size()<f.ans.size()) return; else if(ans.size()>f.ans.size()) ans=f.ans; /* else { if(*ans.rbegin()>*f.ans.rbegin()) ans=f.ans; }*/ } } if(f.ans.size()==7) continue; for(i=0;i<idx;i++) { if(f.state&(1<<i)) continue; for(set<int>::iterator it =f.ans.begin(); it!=f.ans.end();it++) { // printf("%dbitch ",*it); if(*it>b[i]) { fuck p=f; int sum=*it-b[i]; for(set<int> :: iterator it2=f.ans.begin(); it2!=f.ans.end();it2++) { int nu=abs(*it2-sum); // printf("bitch%d ",nu); if(shit[nu]==-1) continue; p.state=(p.state|(1<<shit[nu])); } p.ans.insert(sum); if(!vis[p.state]) { q.push(p); vis[p.state]=true; } } if(*it+b[i]<=b[idx-1]) { fuck p=f; int sum=*it+b[i]; for(set<int> :: iterator it2=f.ans.begin(); it2!=f.ans.end();it2++) { int nu=abs(*it2-sum); if(shit[nu]==-1) continue; p.state=(p.state|(1<<shit[nu])); } p.ans.insert(sum); if(!vis[p.state]) { q.push(p); vis[p.state]=true; } } } } } } int main() { int i,j,n,m; int cas=1; while(scanf("%d",&n)==1&&n) { for(i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); idx=0; memset(vis,false,sizeof(vis)); memset(shit,-1,sizeof(shit)); ans.clear(); for(i=1;i<=n;i++) { if(shit[a[i]]!=-1) continue; b[idx++]=a[i]; shit[a[i]]=i; } for(i=0;i<idx;i++) shit[b[i]]=i; // for(i=0;i<idx;i++) printf("%d ",b[i]);printf(" "); bfs(); set<int> ::iterator it; bool flag=false; printf("Case %d: ",cas++); printf("%d ",ans.size()); for(it=ans.begin();it!=ans.end();it++) { if(flag) printf(" "); printf("%d",*it); flag=true; } printf(" "); } return 0; }