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

IT巨子松老师经过数十年的奋斗，终于打败了所有竞争对手准备一统IT界。此时除了松老师的帝国之外还有N个残存的小公司，松老师打算收购其中的一些。这些公司有a1、a2…an个员工，收购之后松老师打算把员工分给总裁办的K个助理进行管理，为了防止内部矛盾，松老师希望每个助理分到的员工数量都相同。松老师想知道自己最多可以收购多少家公司，使得总的员工数可以平均分配呢？

第一行为一个正整数T，表示有T组数据(T<=20)

每组数据第一行为两个正整数n，k，表示有n家公司(n<=40),以及助理的人数（k<=1000000）

接下来的一行是n个正整数，表示每家公司的员工人数（ai<=5000000）

一个整数m表示最多可以收购多少家公司

2

3 3

1 2 3

5 7

1 10 10 10 10

3

3 

题目链接：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&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;else return 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");}
}