DFS BestCoder Round #49 ($) 1001 Untitled-白红宇

DFS BestCoder Round #49 ($) 1001 Untitled

阅读量：6975 次

发布时间：2019-06-27

本文共 1491 字，大约阅读时间需要 4 分钟。

1 /* 2     DFS：从大到小取模，因为对比自己大的数取模没意义，可以剪枝。但是我从小到大也过了，可能没啥大数据 3 */ 4 /************************************************ 5 Author        :Running_Time 6 Created Time  :2015-8-1 18:57:52 7 File Name     :A.cpp 8 *************************************************/ 9 10 #include 
     
      11 #include 
      
       12 #include 
       
        13 #include 
        
         14 #include 
         
          15 #include 
          
           16 #include 
           
            17 #include 
            
             18 #include 
             
              19 #include 
              
               20 #include 
               
                21 #include 
                
                 22 #include 
                 23 #include 
                  
                   24 #include 
                   
                    25 #include 
                    
                     26 #include 
                     
                      27 using namespace std;28 29 typedef long long ll;30 const int MAXN = 22;31 const int INF = 0x3f3f3f3f;32 const int MOD = 1e9 + 7;33 int a[MAXN];34 bool vis[MAXN];35 int n, ans;36 37 bool cmp(int x, int y) {38 return x > y;39 }40 41 void DFS(int now, int step) {42 for (int i=1; i<=n; ++i) {43 if (vis[i] || now < a[i]) continue;44 if (now % a[i] == 0) {45 ans = min (ans, step + 1); return ;46 }47 vis[i] = true; DFS (now % a[i], step + 1); vis[i] = false;48 }49 }50 51 int main(void) { //HDOJ 5339 Untitled52 int T; scanf ("%d", &T);53 while (T--) {54 int x; scanf ("%d%d", &n, &x);55 for (int i=1; i<=n; ++i) scanf ("%d", &a[i]);56 sort (a+1, a+1+n, cmp);57 if (x < a[n]) {58 puts ("-1"); continue;59 }60 memset (vis, false, sizeof (vis));61 ans = INF; DFS (x, 0);62 if (ans == INF) puts ("-1");63 else printf ("%d\n", ans);64 }65 66 return 0;67 }