【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数
http://acm.hdu.edu.cn/showproblem.php?pid=1557Problem Description
在选举问题中，总共有n个小团体，每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半，则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是：在其所在的获胜联盟中，如果缺少了这个小团体的加入，则此联盟不能成为获胜联盟。一个小团体的权利指数是指：一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。
Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为一个正整数n（0<n<=20）。第二行有n个正整数，分别表示1到n号小团体的票数。
Output
对每组测试数据，在同一个行按顺序输出1到n号小团体的权利指数。
Sample Input
2
1
10
7
5 7 4 8 6 7 5
Sample Output
1
16 22 16 24 20 22 16
#include <iostream>using namespace std;int main(){int t, n, a, i, key, k, total, ans;scanf ("%d", &t);while (t--){memset (ans, 0, sizeof(ans));total = 0;scanf ("%d", &n);for (i = 0; i < n; i++)scanf ("%d", a+i), total += a;total /= 2; //总票数的一半【写成total = (total+1)/2 会错……】//枚举子集【1】~【2的n次方-1】int maxs = 1 << n;for (i = 1; i < maxs; i++){k = 0;int tp = i, j = 0, sum = 0;while (tp){if (tp & 1)//tp的二进制从左往右数第j位是1，则认为a入了集合key = j, sum += a;//记住入了集合的a的元素编号j，并累加票数tp >>= 1; //tp的二进制往右移动，即消去二进制最后一位j++;}if (sum > total) //如果团体的票数超过总票数的一半for (j = 0; j < k; j++)if (sum - a] <= total)ans]++;//如果没了a]就不行，则编号为key的元素为“关键加入者”，该元素权利指数+1}printf ("%d", ans);for (i = 1; i < n; i++)printf (" %d", ans);printf ("\n");}return 0;}
深搜：
#include <iostream>using namespace std;int con, ans, total, n, a, key; //con存放a中元素编号bool visited;void dfs (int x, int sum, int times)//x是元素编号，sum是临时和，times是con中元素个数{ if (times == key) { if (sum > total) for (int i = 0; i < times; i++) if (sum - a] <= total) ans]++; return ; } for (int i = x + 1; i < n; i++) { con = i; dfs (i, sum+a, times+1); }}int main(){ int t, i; scanf ("%d", &t); while (t--) { scanf ("%d", &n); total = 0; for (i = 0; i < n; i++) scanf ("%d", a+i), total += a; total /= 2; memset (ans, 0, sizeof(ans)); for (key = 1; key <= n; key++) //枚举获胜联盟中团体个数 { memset (visited, false, sizeof(visited)); visited = true; dfs (-1, 0, 0); } for (i = 0; i < n - 1; i++) printf ("%d ", ans); printf ("%d\n", ans); } return 0;}
页:
[1]