首页 > 代码库 > 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 }
2017盛大游戏杯 零件组装(状态压缩DP之巧妙枚举子集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。