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

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

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

题意:

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

题解:

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

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

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

技术分享
 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 #define count(x) __builtin_popcount(x)
 5 using namespace std;
 6 
 7 const int N=14;
 8 int t,n,a[N][N],b[N][N],U;
 9 int f[1<<N],g[1<<N],dp[1<<N];
10 
11 int main(){
12     scanf("%d",&t);
13     while(t--)
14     {
15         scanf("%d",&n),U=(1<<n)-1;
16         F(i,0,n-1)F(j,0,n-1)scanf("%d",&a[i][j]);
17         F(i,0,n-1)F(j,0,n-1)scanf("%d",&b[i][j]);
18         mst(dp,63),mst(f,0),mst(g,0),dp[0]=0;
19         F(i,0,U)F(ii,0,n-1)F(jj,ii+1,n-1)
20         if((i&(1<<ii))&&(i&(1<<jj)))f[i]+=a[ii][jj],g[i]+=b[ii][jj];
21         F(i,0,n-1)dp[1<<i]=0;
22         F(i,0,U)for(int j=i;j;j=(j-1)&i)
23         {
24             int ii=j,jj=j^i;
25             if(f[i]-f[ii]-f[jj])
26             dp[i]=min(dp[i],dp[ii]+dp[jj]+(g[i]-g[ii]-g[jj])*max(count(ii),count(jj)));
27         }
28         printf("%d\n",dp[U]);
29     }
30     return 0;
31 }
View Code

 

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