狀態壓縮?
uva?12368?-?Candles? ?2011 - Dhaka
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<string>
5 #include<algorithm>
6 #include<math.h>
7 #include<map>
8 #include<queue>
9 using namespace std;
10 #define LL long long
11 #define nMAX (1<<10+10)
12 #define mMAX 110
13 int ar[25],n;
14 int f[nMAX];
15 bool vis[nMAX][mMAX];
16 struct node{
17 int a,b,num;
18 };
19 void init(){
20 int a[100]; node b[100];
21 for(int x=0;x<(1<<10);x++){
22 int cnta=0,cntb=0;
23 for(int i=0;i<10;i++) if(x&(1<<i)){
24 a[cnta++]=i; vis[x][i]=true;
25 }
26 for(int i=0;i<cnta;i++) for(int j=0;j<cnta;j++) if(i!=j) {
27 int num=a[i]*10+a[j];
28 b[cntb].a=i, b[cntb].b=j, b[cntb++].num=num;
29 vis[x][num]=true;
30 }
31 for(int i=0;i<cnta;i++) for(int j=0;j<cnta;j++) if(i!=j){
32 int num=a[i]+a[j];
33 if(num<=100) vis[x][num]=true;
34 }
35 for(int i=0;i<cnta;i++) for(int j=0;j<cntb;j++) if(i!=b[j].a&&i!=b[j].b){
36 int num=a[i]+b[j].num;
37 if(num<=100) vis[x][num]=true;
38 }
39 for(int i=0;i<cntb;i++) for(int j=0;j<cntb;j++)
40 if(b[i].a!=b[j].a&&b[i].a!=b[j].b
41 &&b[i].b!=b[j].a&&b[i].b!=b[j].b){
42 int num=b[i].num+b[j].num;
43 if(num<=100) vis[x][num]=true;
44 }
45 }
46 }
47 bool ok(int x){
48 for(int i=0;i<n;i++) if(!vis[x][ar[i]]) return false;
49 return true;
50 }
51 int number(int x){
52 int sum=0, p=1;
53 for(int i=0;i<10;i++) if((1<<i)&x) {
54 sum+=i*p; p*=10;
55 }
56 return sum;
57 }
58 int main(){
59 int T=1; init();
60 for(int i=0;i<(1<<10);i++)
61 for(int j=0;j<10;j++) if(i&(1<<j)) f[i]++;
62 f[nMAX-1]=111;
63
64 while(scanf("%d",&n)&&n){
65 for(int i=0;i<n;i++) scanf("%d",&ar[i]);
66 int k=0,ans=nMAX-1;
67 for(int i=0;i<(1<<10);i++) {
68 if(ok(i)&&f[ans]>=f[i]){
69 if(f[ans]==f[i]&&number(ans)>number(i)) ans=i;
70 else if(f[ans]!=f[i])ans=i;
71 }
72 }
73 printf("Case %d: %d\n",T++,number(ans));
74 }
75 }
