刻度尺 (Ruler,Beijing 2006,LA 3667)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 using namespace std;
11 const double eps = 1e-8;
12 #define MAXN 10000001
13 struct node
14 {
15     set<int> t;
16     int c;
17 };
18 int n;
19 int d[55];
20 char hash[MAXN];
21 set<int> ans;
22 
23 bool found;
24 int N=1,MAX,stats;
25 
26 void bfs()
27 {
28    node temp;temp.t.insert(0);temp.c=0;
29    queue<node> q;
30    q.push(temp);
31    while(!q.empty())
32    {
33        node cur=q.front();q.pop();
34        if(cur.c==stats)
35        {
36            if(cur.t.size()<ans.size())
37             ans=cur.t;
38            else if(*cur.t.end()<*ans.end())
39             ans=cur.t;
40         return;
41        }
42 
43        for(set<int>::iterator it=cur.t.begin();it!=cur.t.end();it++)
44        {
45            node next;
46            for(int i=0;i<n;i++)
47            {
48                if(cur.c&(1<<i))continue;
49                int v=*it+d[i];
50                if(cur.t.find(v)!=cur.t.end())continue;
51                if(v>MAX)continue;
52                next=cur;
53                next.t.insert(v);
54 
55                for(set<int>::iterator it1=cur.t.begin();it1!=cur.t.end();it1++)
56                {
57                 int x=abs(v-*it1);
58                 if(hash[x]!=-1){
59                     next.c|=(1<<hash[x]);
60                 }
61                }
62                if(next.c!=cur.c)q.push(next);
63            }
64        }
65    }
66 }
67 
68 int main()
69 {
70 
71     while(scanf("%d",&n),n!=0)
72     {
73         found=false;
74         memset(hash,-1,sizeof(hash));
75         for(int i=0;i<n;i++)
76         {
77             scanf("%d",&d[i]);
78             ans.insert(d[i]);
79         }
80         sort(d,d+n);
81         n=unique(d,d+n)-d;
82         MAX=d[n-1];
83         for(int i=0;i<n;i++)
84             hash[d[i]]=i;
85         stats=(1<<n)-1;
86         bfs();
87         printf("Case %d:
%d
",N++,ans.size());
88         for(set<int>::iterator it=ans.begin();it!=ans.end();it++)
89         printf("%d ",*it);
90         printf("
");
91 
92     }
93 
94 
95     return 0;
96 }