发布时间: 2017年7月9日 18:17 最后更新: 2017年7月9日 21:04 时间限制: 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 #include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 14, M = (1 << 14) + 2, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int con[N][N]; int cost[N][N]; int num2[M]; int f[M]; int n; int num[M]; int a[M][14]; int VAL(int x, int y) { bool isCon = 0; int val = 0; for (int i = 0; i < num[x]; ++i) { int xx = a[x][i]; for (int j = 0; j < num[y]; ++j) { int yy = a[y][j]; isCon |= con[xx][yy]; val += cost[xx][yy]; } } if (!isCon)return inf; return val * max(num[x], num[y]); } int main() { for (int i = 1; i <= (1 << 14); ++i) { num2[i] = num2[i >> 1] + (i & 1); for (int j = 0; j < 14; ++j)if (i >> j & 1) { a[i][num[i]++] = j; } } scanf("%d", &casenum); for (casei = 1; casei <= casenum; ++casei) { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &con[i][j]); } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &cost[i][j]); } } MS(f, 63); f[0] = 0; int top = (1 << n) - 1; for (int i = 1; i <= top; ++i) { if (num2[i] == 1) { f[i] = 0; continue; } for (int j = i - 1 & i; j; j = j - 1 & i) { int k = i ^ j; if(f[j] != inf && f[k] != inf)//不要忽视可能会溢出的特殊情况 gmin(f[i], f[j] + f[k] + VAL(j, k)); } } printf("%d\n", f[top]); } return 0; } /* 【trick&&吐槽】 分块真是个好东西 【题意】 http://acmoj.shu.edu.cn/problem/420/ 【分析】 这题可以通过枚举子集（复杂度为3^n）的方法，知道合并的两方， if(f[j] != inf && f[k] != inf) gmin(f[i], f[j] + f[k] + VAL(j, k)); 但是这里VAL(j, k)会消耗我们n^2级别的运算量。 【时间复杂度&&优化】 O(3^n * n * n) */【“盛大游戏杯”第15届上海大学程序设计联赛 L】【状压DP 枚举子集 + 分块预处理 分块做法】零件组装
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 14, M = 1 << 14, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int CON[N][N]; int COST[N][N]; int num2[M]; //num2[mask]表示mask的二进制表示k中有多少个1 int rev2[M]; //rev2[mask]表示mask（2^k）的k是多少 int p_con[2][2][N][M]; int p_cost[2][2][N][M]; int con[2][2][1 << 7][1 << 7]; int cost[2][2][1 << 7][1 << 7]; int f[M]; int n, h, top; int val(int x, int tp) { if(tp == 0) return x & top; else return x >> h; } int VAL(int x, int y) { bool isCon = 0; int ret = 0; for (int k = 0; k < 2; ++k) { for (int u = 0; u < 2; ++u) { isCon |= con[k][u][val(x, k)][val(y, u)]; ret += cost[k][u][val(x, k)][val(y, u)]; } } if (!isCon)return inf; else return ret * max(num2[x], num2[y]); } int main() { for (int i = 1; i < (1 << 14); ++i) num2[i] = num2[i >> 1] + (i & 1); for (int i = 0; i < 14; ++i)rev2[1 << i] = i; scanf("%d", &casenum); for (casei = 1; casei <= casenum; ++casei) { scanf("%d", &n); h = (n + 1) / 2; top = (1 << h) - 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &CON[i][j]); } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &COST[i][j]); } } MS(p_con, 0); MS(p_cost, 0); for (int x = 0; x < h; ++x) { for (int j = 1; j <= top; ++j) { for (int y = 0; y < h; ++y)if (j >> y & 1) { for (int k = 0; k < 2; ++k) { for (int u = 0; u < 2; ++u) { p_con[k][u][x][j] |= CON[x + k * h][y + u * h]; p_cost[k][u][x][j] += COST[x + k * h][y + u * h]; } } } } } for (int i = 1; i <= top; ++i) { int x = rev2[i & -i]; for (int j = 1; j <= top; ++j) { for (int k = 0; k < 2; ++k) { for (int u = 0; u < 2; ++u) { con[k][u][i][j] = con[k][u][i ^ 1 << x][j] | p_con[k][u][x][j]; cost[k][u][i][j] = cost[k][u][i ^ 1 << x][j] + p_cost[k][u][x][j]; } } } } MS(f, 63); f[0] = 0; int top = (1 << n) - 1; for (int i = 1; i <= top; ++i) { if (num2[i] == 1) { f[i] = 0; continue; } for (int j = i - 1 & i; j; j = j - 1 & i) { int k = i ^ j; if (f[j] != inf && f[k] != inf)//不要忽视可能会溢出的特殊情况 gmin(f[i], f[j] + f[k] + VAL(j, k)); } } printf("%d\n", f[top]); } return 0; } /* 【trick&&吐槽】 分块真是个好东西 【题意】 http://acmoj.shu.edu.cn/problem/420/ 【分析】 这题可以通过枚举子集（复杂度为3^n）的方法，知道合并的两方， if(f[j] != inf && f[k] != inf) gmin(f[i], f[j] + f[k] + VAL(j, k)); 但是这里VAL(j, k)会消耗我们n^2级别的运算量。 而如果我们分块预处理，就是预处理出 v[2][2][2^7][2^7]这样一个数组 比如v[0][1][5][16]就表示—— 前一半是5，后一半是16<<7 这两部分状态之间的碰撞程度 我们这里是用分块预处理的，进而做到3^n*4的复杂度 【时间复杂度&&优化】 O(3^n * 4) */