【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数

基德KID.1412

http://acm.hdu.edu.cn/showproblem.php?pid=1557


Problem 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[25], i, key[25], k, total, ans[25];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[j]入了集合key[k++] = j, sum += a[j];//记住入了集合的a的元素编号j，并累加票数tp >>= 1;    //tp的二进制往右移动，即消去二进制最后一位j++;}if (sum > total)    //如果团体的票数超过总票数的一半for (j = 0; j < k; j++)if (sum - a[key[j]] <= total)ans[key[j]]++;//如果没了a[key[j]]就不行，则编号为key[j]的元素为“关键加入者”，该元素权利指数+1}printf ("%d", ans[0]);for (i = 1; i < n; i++)printf (" %d", ans);printf ("\n");}return 0;}

深搜：
#include <iostream>using namespace std;int con[25], ans[25], total, n, a[25], key;    //con存放a中元素编号bool visited[25];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[con] <= total)                    ans[con]++;        return ;    }    for (int i = x + 1; i < n; i++)    {        con[times] = 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[0] = true;            dfs (-1, 0, 0);        }        for (i = 0; i < n - 1; i++)            printf ("%d ", ans);        printf ("%d\n", ans[n-1]);    }    return 0;}