2017盛大游戏杯 零件组装(状态压缩DP之巧妙枚举子集)

题目链接：2017盛大游戏杯 零件组装

题意：

有n个零件，给你相邻关系和排斥关系，每两块零件组装起来有一个代价，问最少的代价总和是多少。

题解：

考虑状态压缩，dp[i]表示i这个集合为一个零件块。

那么要枚举一下i的子集。O(3^n).

先要预处理一下每个集合的排斥个数和相邻个数，然后容斥一下就可以了。

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=a;i<=b;++i)
#define count(x) __builtin_popcount(x)
using namespace std;

const int N=14;
int t,n,a[N][N],b[N][N],U;
int f[1<<N],g[1<<N],dp[1<<N];

int main(){
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n),U=(1<<n)-1;
        F(i,0,n-1)F(j,0,n-1)scanf("%d",&a[i][j]);
        F(i,0,n-1)F(j,0,n-1)scanf("%d",&b[i][j]);
        mst(dp,63),mst(f,0),mst(g,0),dp[0]=0;
        F(i,0,U)F(ii,0,n-1)F(jj,ii+1,n-1)
        if((i&(1<<ii))&&(i&(1<<jj)))f[i]+=a[ii][jj],g[i]+=b[ii][jj];
        F(i,0,n-1)dp[1<<i]=0;
        F(i,0,U)for(int j=i;j;j=(j-1)&i)
        {
            int ii=j,jj=j^i;
            if(f[i]-f[ii]-f[jj])
            dp[i]=min(dp[i],dp[ii]+dp[jj]+(g[i]-g[ii]-g[jj])*max(count(ii),count(jj)));
        }
        printf("%d
",dp[U]);
    }
    return 0;
}