uva 1377 - Ruler(BFS)

题目链接：uva 1377 - Ruler

题目大意：给出一些刻度，要求制作一把尺子，可以直接测量出给出的刻度，要求尺子尽量短，并且刻度尽量少，注意：所标记的刻度数不会大于7，题目限制。

解题思路：注意题目中的限制，说刻度数最大为7，C（2，7） = 21，也就是说最多能表示21个长度，题目所给出的50个长度有一半多式重复的长度。让后题目还有一个限制条件，说尺子尽量短，也就是说最大的刻度要尽量小（因为所标的刻度不一定是给出刻度的某一个，例5 7 8 10 100）。我的做法是广搜，每个一个状态记录已选刻度，可表达的刻度（二进制），每次添加第一个不能测量的长度。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 50; const int M = 100005; typedef set
        
         ::iterator iter; struct state { int s, now; set
         
           rec; }ans; int n, c, d[N], v[M]; void init() { c = 0; ans.rec.clear(); memset(v, 0, sizeof(v)); int a; for (int i = 0; i < n; i++) { scanf("%d", &a); if (!v[a]) { d[c++] = a; v[a] = 1; } } sort(d, d + c); memset(v, -1, sizeof(v)); for (int i = 0; i < c; i++) v[d[i]] = i; } bool cmp(state a, state b) { if (a.rec.size() != b.rec.size()) return a.rec.size() > b.rec.size(); iter p = a.rec.begin(), q = b.rec.begin(); while (p != a.rec.end()) { if (*p != *q) return *p > *q; p++; q++; } return false; } state add(state u, int k) { for (iter i = u.rec.begin(); i != u.rec.end(); i++) { int t = abs(*i - k); if (v[t] == -1) continue; if ((u.s & (1<
          
            que; u.s = 0; u.rec.insert(0); que.push(u); while (!que.empty()) { u = que.front(); que.pop(); if (ans.rec.size() != 0 && ans.rec.size() < u.rec.size()) return; if (u.s == tmp) { if (ans.rec.size() == 0 || cmp(ans, u)) ans = u; } else { if (u.rec.size() == 7) continue; for (int i = 0; i < c; i++) if ((u.s & (1<
           
             d[i]) que.push(add(u, *j - d[i])); } break; } } } } void solve() { bfs(); int flag = false; printf("%lu\n", ans.rec.size()); for (iter i = ans.rec.begin(); i != ans.rec.end(); i++) { if (flag) printf(" "); printf("%d", *i); flag = true; } printf("\n"); } int main() { int cas = 1; while (scanf("%d", &n) == 1 && n) { init(); printf("Case %d:\n", cas++); solve(); } return 0; }