题目描述
在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人的死亡宴会。为了不让日本人发现，自然需要一番乔装打扮。但由于天生材质的原因，每个人和每个人之间的相似度是不同的。由于我们这是编程题，因此情况就变成了金陵n钗。给出n个女人和n个学生的相似度矩阵，求她们之间的匹配所能获得的最大相似度。
所谓相似度矩阵是一个nn的二维数组like[i][j]。其中i,j分别为女人的编号和学生的编号，皆从0到n-1编号。like[i][j]是一个0到100的整数值，表示第i个女人和第j个学生的相似度，值越大相似度越大，比如0表示完全不相似，100表示百分之百一样。每个女人都需要找一个自己代替的女学生。
最终要使两边一一配对，形成一个匹配。请编程找到一种匹配方案，使各对女人和女学生之间的相似度之和最大。
输入
第一行一个正整数n表示有n个秦淮河女人和n个女学生
接下来n行给出相似度，每行n个0到100的整数，依次对应二维矩阵的n行n列。
输出
仅一行，一个整数，表示可获得的最大相似度。
样例输入
4
97 91 68 14
8 33 27 92
36 32 98 53
73 7 17 82
*样例输出
354
和n皇后类似，只不过对角线可以有。暴力就超时了。
用状态压缩，用n为01来表示当前的可选状态，0表示不可选，1表示可选。
所以对于第一行，所有都可选，也就是全1的状态。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//状压+记忆化搜索
//state的二进制中1表示当前行的这个位可选
int a[15][15];
int dp[15][1<<14]; //dp[i][j]表示第i行选状态为j的最大值
int n;
int dfs(int line, int state){
if (dp[line][state]!=-1){
return dp[line][state];
}
int maxx=0;
if (line==n-1){
for (int i=0; i<n; i++){
int t=(1<<i);
if (t&state){
return a[line][i];
}
}
}else{
for (int i=0; i<n; i++){
int t=(1<<i);
if (t&state){
maxx=max(maxx, a[line][i]+dfs(line+1, state-t)); //这一行选第i位，并标记
}
}
}
return dp[line][state]=maxx;
}
int main(){
memset(dp, -1, sizeof(dp));
scanf("%d", &n);
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
scanf("%d", &a[i][j]);
}
}
int state=(1<<n)-1;
printf("%d", dfs(0, state));
return 0;
}
AI 代码解读
