SHU金马五校赛 L.零件组装 【状压DP】

零件组装 发布时间: 2017年7月9日 20:20 最后更新: 2017年7月10日 21:12 时间限制: 1000ms 内存限制: 128M 描述 现有n个零件，小Y花费了很多时间来收集它们，现在他想把零件拼在一起，拼完就可以召唤神龙了。已知零件之间存在相邻的关系，拥有相邻关系的零件在最终的组装结果中就是相邻的，并且组装过程中每次只能通过相邻关系来组合零件。小Y每次可以选择两个零件（也可以是两个零件块，或一个零件与一个零件块）拼起来，成为一个零件块，但要求拼接时必须在两个零件块（或零件）之间存在相邻的零件。除此之外这些零件两两之间有类似于磁力的排斥关系，当将两个零件或者零件块拼接在一起的时候，会受到两边的零件间的排斥力，排斥力的大小=两边零件的相互排斥对数*单侧零件个数的最大值（拼接完成的零件组合体中的零件之间排斥不计）。现在已知零件间的相邻关系和排斥关系，小Y自然想知道如何拼接不费力，因此需要求出将这些零件组装起来的最优方案，使得所有步骤的排斥力之和最小。 输入 第一行有一个整数T表示数据组数。（T<=20） 接着有T组数据，每组数据第一行是整数n表示零件个数。 接着依此有两个n∗n的矩阵，都只由0和1构成。(2<=n<=14) 其中第一个矩阵表示零件两两之间的相邻关系，第i行第j列为1表示第i个零件与第j个零件相邻， 第二个矩阵表示零件两两之间的排斥关系，第i行第j列为1表示第i个零件与第j个零件排斥。 数据保证矩阵根据对角线对称，并保证通过零件的相邻关系可以最终拼接完成。 输出 每组输入一个整数表示拼接过程的最小排斥力之和。 样例输入1 复制 1 4 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 样例输出1 6 提示 样例的组装方法是现将零件2和零件3拼起来，受到排斥力1*1 然后将零件1和零件4拼起来，受到排斥力1*1 最后将零件块{2,3}和{1,4}拼起来，受到排斥力2*2.

直接状态压缩dp d[i|j]=min(d[i|j],d[i]+d[j]+cost(i,j)) 计算 cost(i,j)−−>i与j 状态合并的花销需要 O(n2) 总复杂度 O(22n∗n2) 直接爆炸

枚举状态i 再枚举i的子状态a b=a^i d[i]=min(d[i],d[a]+d[b]+cost(a,b)) 情况数相当于枚举每个状态 包含在集合a,集合b,集合a与b都不含 O(3n) 计算 cost−>O(3n∗n3) ,继续TLE

瓶颈在于cost()的计算 如果 hcNum[i]=i状态下,i内部零件的互斥对数 若i状态下,与零件j存在相邻关系−>xlIdx[i]>>j & 1==true 则状态a,b互斥零件对数为 hcNum[a|b]−hcNum[a]−hcNum[b] 则 cost(a,b)=max(size[a],size[b])∗(hcNum[a|b]−hcNum[a]−hcNum[b]) hcNum,size,xlIdx都不难预处理出来,这样cost(a,b)就能在O(1)内求出 最终O(3n)

#include<stdio.h> #include<iostream> #include<string> #include<vector> #include<stdlib.h> #include<math.h> #include<string.h> #include<algorithm> #define ll long long #define pii pair<int,int> #define MEM(a,x) memset(a,x,sizeof(a)) #define lowbit(x) ((x)&-(x)) using namespace std; const int inf=0x3f3f3f3f; const int N = 15; const int M = (1<<N)+1; int xl[N][N],hc[N][N];//相邻 互斥 int hcNum[M];//i状态内部 零件互斥对数 int xlIdx[M];//i状态下 第k位为1 则与k存在相邻关系 int size[M];//i状态 有多少个零件 ll d[M];//拼成i 最小花销 int getSize(int x){ int size=0; while(x){ size+=x&1; x>>=1; } return size; } int getHcNum(int x,int n){ vector<int>vec; for(int i=0;i<n;++i){ if((x>>i)&1){ vec.push_back(i); } } int ans=0; for(int i=0;i<vec.size();++i){ for(int j=i+1;j<vec.size();++j){ int&a=vec[i],&b=vec[j]; if(hc[a][b]){ ++ans; } } } return ans; } int getXlIdx(int x,int n){ vector<int>vec; for(int i=0;i<n;++i){ if((x>>i)&1){ vec.push_back(i); } } int ans=0; for(int i=0;i<vec.size();++i){ for(int j=0;j<n;++j){ if(xl[vec[i]][j]){ ans|=(1<<j); } } } return ans; } void findSub(int sup){ int sub=sup; do{ /*对子集处理*/ int a=sub,b=sup^sub; if(xlIdx[a]&b){//a与b存在相邻关系 d[a|b]=min(d[a|b],d[a]+d[b]+max(size[a],size[b])*(hcNum[a|b]-hcNum[a]-hcNum[b])); } sub=(sub-1)⊃ }while(sub); } ll dp(int n){ MEM(d,0x3f); d[0]=0; for(int i=0;i<n;++i){ d[1<<i]=0; } for(int i=0,ed=(1<<n);i<ed;++i){ size[i]=getSize(i); hcNum[i]=getHcNum(i,n); xlIdx[i]=getXlIdx(i,n); findSub(i); } return d[(1<<n)-1]; } int main() { //freopen("/home/lu/code/r.txt","r",stdin); int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ scanf("%d",&xl[i][j]); } } for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ scanf("%d",&hc[i][j]); } } printf("%lld\n",dp(n)); } return 0; }