NOJ 2030 收购计划 (枚举＋DFS 好题)

33

题目链接：?&method=showdetail&id=2030

题目分析：乍一看有点像搜索神题sticks，其实是个单向深搜，01背包的思想，对于每个值取或者不取

说一下几个剪枝

1.若总和是k的倍数，直接输出n

2.若当前使用的加上没使用的比枚举值小，说明该情况无解

这样做跑了109ms

#include <cstdio>#include <cstring>using namespace std;int a[45], n, k, ans;bool DFS(int i, int tot, int cnt){if(n – i + cnt < ans)return false;if(cnt == ans){if(tot % k == 0)return true;elsereturn false;}if(DFS(i + 1, tot + a[i], cnt + 1))return true;if(DFS(i + 1, tot, cnt))return true;return false;}int main(){int T;scanf("%d", &T);while(T–){bool flag = false;int sum = 0;scanf("%d %d", &n, &k);for(int i = 0; i < n; i++){scanf("%d", &a[i]);sum += a[i];}if(sum % k == 0){printf("%d\n", n);continue;}for(int i = n – 1; i >= 1; i–){ans = i;if(DFS(0, 0, 0)){printf("%d\n", ans);flag = true;break;}}if(!flag)printf("0\n");}}

大神31ms的做法：

通过同余来搜索答案，，记总和对k取余为mod，然后再在这里面找一组和对k的余数为mod，差值就是答案，对于所有的a[i]如果a[i]本身就是k的倍数就可以不用放在待搜索的序列里了

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[45];int n, k, nn, MOD, tmp;int cmp(int a, int b){return a > b;}bool DFS(int s, int mod, int used){if((nn – s + 1 + used) < tmp)return false;if(used == tmp){if(mod == MOD)return true;elsereturn false;}if(DFS(s + 1, (mod + a[s]) % k, used + 1))return true;if(DFS(s + 1, mod, used))return true;return false;}int main(){int T;scanf("%d", &T);while(T–){int get;MOD = 0;memset(a, 0, sizeof(a));scanf("%d %d", &n, &k);for(int i = 0; i < n; i++){scanf("%d", &get);a[i] = get % k;MOD = (MOD + a[i]) % k;}if(MOD == 0){printf("%d\n", n);continue;}sort(a, a + n, cmp);nn = n;bool flag = false;while(a[nn – 1] == 0) //这里也是一个剪枝nn–;for(int i = 1; i < nn; i++){tmp = i;if(DFS(0, 0, 0)){printf("%d\n", n – i);flag = true;break;}}if(!flag)printf("0\n");}}

奋斗令我们的生活充满生机，责任让我们的生命充满意义！