首页 > 代码库 > TOJ 4095 BoatBurglary 分治

TOJ 4095 BoatBurglary 分治

2024-07-17 09:14:17   221人阅读

http://acm.tju.edu.cn/toj/showp4095.html

题意：

N个物品，N <= 30，每个有重量w[i]，w[i] <= 10^9，现在重量少了D，问可能少了几个物品，判断是否多解和无解，唯一解输出少掉的物品数量。

分析：

如果重量没那么大就是一个简单的背包，这个数据范围用背包做状态根本存不下。然后脑抽了一直在搜索，一直Tle一直Tle。。其实后面搜索策略已经优化的不错了，只搜一半的层数，然后搜出来的集合的sum以及补集的sum分别判断是否等于D。但是这还是逃不过C(15, 30)的状态数。

请教了学长得到一个分治算法。。折半处理，枚举选和不选，分别是2^15，然后排序，对于一侧的一个值，找另一侧是否有一个值使他们俩相加等于D就可以了。复杂度是o(2^(n/2)lg(2^(n/2)))

然后我wa了好几次，一方面是自己写萎了，一方面不知道题目有没有trick。一个是D的范围，不开longlong可能读入就会爆，一个是w[i]和D貌似有可能为0，然后该怎么处理为0的情况我也晕了。。反正底下程序是AC的。。

 

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 using namespace std;  5   6 struct arr{  7     int num;  8     long long sum;  9 } a[100000], b[100000]; 10 int T, n, sizea, sizeb; 11 long long D, w[40]; 12 bool legal[40]; 13 bool cmp(arr a, arr b) 14 { 15     return a.sum < b.sum; 16 } 17 int main() 18 { 19     scanf("%d", &T); 20     int cas = 0; 21     while(T--) 22     { 23         scanf("%d %lld", &n, &D); 24         for (int i = 0; i < n; i++) scanf("%lld", w+i); 25         sizea = sizeb = 1; 26         a[0].num = b[0].num = a[0].sum = b[0].sum = 0; 27         for (int i = 0; i <= n/2; i++){ 28             int tmp = sizea; 29             for (int j = 0; j < tmp; j++){ 30                 a[sizea].num = a[j].num + 1; 31                 a[sizea++].sum = a[j].sum + w[i]; 32             } 33         }  34         for (int i = n/2+1; i < n; i++){ 35             int tmp = sizeb; 36             for (int j = 0; j < tmp; j++){ 37                 b[sizeb].num = b[j].num + 1; 38                 b[sizeb++].sum = b[j].sum + w[i]; 39             } 40         } 41         sort(a, a+sizea, cmp); 42         sort(b, b+sizeb, cmp); 43         int count = 0, ans; 44         memset(legal, 0, sizeof(legal)); 45         for (int i = 0; i < sizea; i++){ 46             if (a[i].sum > D || count > 1) break; 47             if (a[i].sum == D){ 48                 int number = a[i].num; 49                 if (!legal[number]){ 50                     legal[number] = true; 51                     count ++; 52                     ans = number; 53                 } 54             } 55             if (a[i].sum <= D){ 56                 long long need = D - a[i].sum; 57                 int l = 0, r = sizeb-1, pos = -1; 58                 while (l <= r) 59                 { 60                     int mid = (l + r) >> 1; 61                     if (b[mid].sum == need){ 62                         pos = mid; 63                         break; 64                     } 65                     else if (b[mid].sum < need) l = mid + 1; 66                     else r = mid - 1; 67                 } 68                 if (pos != -1){ 69                     int tmp = pos; 70                     while(pos < sizeb && b[pos].sum == b[tmp].sum){ 71                         int number = a[i].num + b[pos].num; 72                         if (!legal[number]){ 73                             legal[number] = true; 74                             count ++; 75                             ans = number; 76                         } 77                         pos ++; 78                     } 79                     pos = tmp-1; 80                     while(pos >= 0 && b[pos].sum == b[tmp].sum){ 81                         int number = a[i].num + b[pos].num; 82                         if (!legal[number]){ 83                             legal[number] = true; 84                             count ++; 85                             ans = number; 86                         } 87                         pos --; 88                     } 89  90                 } 91             } 92         } 93         cas ++; 94         printf("Case #%d: ", cas); 95         if (count == 0) printf("IMPOSSIBLE\n"); 96         else if (count > 1) printf("AMBIGIOUS\n"); 97         else printf("%d\n", ans); 98     } 99     return 0;100 }

 


联系
我们