UVa 1377 / LA 3667 Ruler

之前WA是被这组数据卡掉了：
5 15 25 35
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <queue>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 struct node
 10 {
 11     int Haash;
 12     int use[8];
 13     int count;
 14 };
 15 
 16 
 17 bool vis[ (1 << 22) + 10 ];
 18 int d[54];
 19 int n, cnt;
 20 int idx[1000100];
 21 
 22 bool check( int a, int cur )
 23 {
 24     for ( int i = 0; i < cur; ++i )
 25         if ( d[i] == a ) return false;
 26     return true;
 27 }
 28 
 29 bool IfEnd( int a )
 30 {
 31     //printf( "all = %d\n", ( 1 << cnt ) - 1 );
 32     if ( a == (1 << cnt) - 1 ) return true;
 33     return false;
 34 }
 35 
 36 void chuli( node &cur, int add )
 37 {
 38     for ( int i = 0; i < cur.count; ++i )
 39     {
 40         int c = abs( add - cur.use[i] );
 41         if ( idx[c] != -1 ) cur.Haash |= ( 1 << idx[c] );
 42     }
 43 
 44     cur.use[ cur.count++ ] = add;
 45 
 46     sort( cur.use, cur.use + cur.count );
 47 
 48     return;
 49 }
 50 
 51 bool IfSame( int *num, int nn, int tar )
 52 {
 53     for ( int i = 0; i < nn; ++i )
 54         if ( num[i] == tar ) return true;
 55 
 56     return false;
 57 }
 58 
 59 node BFS()
 60 {
 61     memset( vis, false, sizeof(vis) );
 62     queue<node> Q;
 63 
 64     node st;
 65     st.Haash = 1;
 66     st.count = 1;
 67     st.use[0] = 0;
 68     vis[ st.Haash ] = true;
 69     Q.push( st );
 70 
 71     while ( !Q.empty() )
 72     {
 73         node cur = Q.front();
 74         Q.pop();
 75         //printf( "cnt=%d last=%d hash=%d\n", cur.count, cur.last, cur.Haash );
 76         if ( IfEnd( cur.Haash ) ) return cur;
 77 
 78         for ( int i = 0; i < cur.count; ++i )
 79         {
 80             for ( int j = 0; j < cnt; ++j )
 81             {
 82                 if ( cur.Haash & ( 1 << j ) ) continue;
 83 
 84                 int x = cur.use[i] + d[j];
 85                 if ( IfSame( cur.use, cur.count, x ) || x > d[ cnt - 1 ] ) continue;
 86 
 87                 node temp = cur;
 88                 chuli( temp, x );
 89 
 90                 if ( !vis[ temp.Haash ] )
 91                 {
 92                     vis[ temp.Haash ] = true;
 93                     if ( IfEnd( temp.Haash ) ) return temp;
 94 
 95                     Q.push(temp);
 96                 }
 97             }
 98 
 99             for ( int j = 0; j < cnt; ++j )
100             {
101                 if ( cur.Haash & ( 1 << j ) ) continue;
102 
103                 int x = cur.use[i] - d[j];
104                 if ( IfSame( cur.use, cur.count, x ) || x > d[ cnt - 1 ] || x < 0 ) continue;
105 
106                 node temp = cur;
107                 chuli( temp, x );
108 
109                 if ( !vis[ temp.Haash ] )
110                 {
111                     vis[ temp.Haash ] = true;
112                     if ( IfEnd( temp.Haash ) ) return temp;
113 
114                     Q.push(temp);
115                 }
116             }
117         }
118     }
119 
120     return st;
121 }
122 
123 int main()
124 {
125     int cas = 0;
126     while ( scanf( "%d", &n ), n )
127     {
128         d[0] = 0;
129         cnt = 1;
130         for ( int i = 0; i < n; ++i )
131         {
132             int a;
133             scanf( "%d", &a );
134             if ( check( a, cnt ) ) d[ cnt++ ] = a;
135         }
136         sort( d, d + cnt );
137 
138         memset( idx, -1, sizeof(idx) );
139         for ( int i = 0; i < cnt; ++i ) idx[ d[i] ] = i;
140 
141         node ans = BFS();
142 
143         printf( "Case %d:\n", ++cas );
144         printf( "%d\n", ans.count );
145         for ( int i = 0; i < ans.count; ++i )
146         {
147             if ( i ) putchar(' ');
148             printf( "%d", ans.use[i] );
149         }
150         puts("");
151     }
152     return 0;
153 }