权利指数

2
1
10
7
5 7 4 8 6 7 5

1
16 22 16 24 20 22 16

二进制枚举代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 25
int t,n;
int a[maxn];
bool vis[maxn];
int b[maxn];
int main()
{
    freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ss=0;
        memset(b,0,sizeof b);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            ss+=a[i];
        }
        int sum=0;
        for(int i=0;i<(1<<n);i++){
            sum=0;
            memset(vis,0,sizeof vis);
            for(int j=0;j<n;j++){
                if(i&(1<<j)){sum+=a[j];vis[j]=1;}
            }
            if(sum>ss/2){
                for(int k=0;k<n;k++){
                    if(vis[k]&&sum-a[k]<=ss/2)b[k]++;
                }
            }
        }
        for(int i=0;i<n-1;i++){
            printf("%d ",b[i]);
        }
        printf("%d\n",b[n-1]);
    }
}

dfs代码，选与不选，和二进制枚举在本质上是一样的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 25
int a[maxn];
bool vis[maxn];
int ss;
int b[maxn];
int n;
void dfs(int dep,int sum){
   if(dep>=n){
   if(sum*2>ss){
   for(int i=0;i<n;i++){
    if(vis[i]&&sum-a[i]<=ss/2)
        b[i]++;
   }
   }
   return;
   }
   vis[dep]=1;
   dfs(dep+1,sum+a[dep]);
   vis[dep]=0;
   dfs(dep+1,sum);

}
int main()
{
     freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ss=0;
        memset(b,0,sizeof b);
        memset(vis,0,sizeof vis);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            ss+=a[i];
        }
        dfs(0,0);
         for(int i=0;i<n-1;i++){
            printf("%d ",b[i]);
        }
        printf("%d\n",b[n-1]);
    }
}

HDU 1557 权利指数

原文：http://blog.csdn.net/u013497977/article/details/44655211