LightOJ 1235 - Coin Change (IV) (折半枚举)

题目链接：

　　http://www.lightoj.com/volume_showproblem.php?problem=1235

题目描述：

　　给出n个硬币，每种硬币最多使用两次，问能否组成K面值？

解题思路：

　　因为K草鸡大，尽管n很小，但是2^n很大，无法用背包做到O(nK)的复杂度。如果暴力枚举复杂度立马飙升到O(2^))。···········

　　所以引进一种新的算法，折半查找：把所要枚举的值，先把前部分的值所有情况枚举出来，再把后部分的值所有情况枚举出来并排序，结合二分进行查找。 这样可以把复杂度降到O(2^*log(n))。

　　最近不做题，感觉自己萌萌哒。大家玩敲七，到我这里，我总是一脸懵逼的样子。希望一天一个dp，到老也能萌萌哒  (。・`ω´・)

代码：

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define maxn 20000

 int cnt1, cnt2, k, n, num;

 int a1[maxn], a2[maxn], b[];

 void dfs (int sum, int x)

 {

     if (x == num)

     {

         num == n/ ? a1[cnt1++] = sum : a2[cnt2++] = sum;

         return ;

     }

     for (int i=; i<; i++)

         dfs (sum+b[x]*i, x+);

 }

 bool sreach (int x)

 {

     int low = , high = cnt2-;

     while (low <= high)

     {

         int mid = (low + high) / ;

         if (a1[x] + a2[mid] == k)

             return true;

         else if (a1[x] + a2[mid] > k)

             high = mid - ;

         else

             low = mid + ;

     }

     return false;

 }

 int main ()

 {

     int T, l = ;

     scanf ("%d", &T);

     while (T --)

     {

         scanf ("%d %d", &n, &k);

         for (int i=; i<n; i++)

             scanf ("%d", &b[i]);

         cnt1 = cnt2 = ;

         num = n / ;

         dfs (, );

         num = n;

         dfs (, n/);

         sort (a2, a2 + cnt2);

         int i;

         for (i=; i<cnt1; i++)

         {

             if (sreach (i))

                 break;

         }

         if (i == cnt1) printf("Case %d: No\n", l++);

         else printf ("Case %d: Yes\n", l++);

     }

     return ;

 }