蓝桥杯 ADV-151 算法提高 金陵十三钗 求解题思路

Question

金陵十三钗
　
问题描述
　
　　所谓相似度矩阵是一个n*n的二维数组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
数据规模和约定
　　对于70%的数据，n<=10
　　对于100%的数据，n<=13
样例说明
　　最大相似度为91+92+93+73=354

Answer 1

对于70%的数据,直接用全排列枚举出每个女生对应的人然后求解,取最大值,时间复杂度是O(n*n!),对于n<=10，是可以接受的

对于100%的数据，可以采用状态压缩的办法进行动态规划：

dp[i][j]表示现在进行到i个女人，被占用学生的状态为j的最大制。

将状态j表示成二进制，第k位为1 表示第k个学生已经被占用了。

比如j=3,二进制是00000011,表示第1和第2个学生已经被占用。

对于初始状态：

dp[0][j]=0    

转移方程是：

dp[i][j]=max(dp[i-1][k]+like[i][t]） 

其中t是j中其中1个1的位置，k是j把第t位变成0的数，把所有t找一边取个最大值再+like[i][t],就是dp[i][j] 

答案就是dp[n][2^n-1]

时间复杂度应该是O(n*2^n)

考虑到对于所有i，只和i-1项有关，所以可以减少一维空间消耗

对于n<=13是可以秒出的。

最后再贴一份刚写的新鲜的代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 15
using namespace std;
const int maxzt=(1<<13);   //最大的状态数,
int dp[maxzt];
int like[MAXN][MAXN],n;
int numberOfOne(int num){ //num 二进制中1的个数
    int cnt=0;
    while(num){
        cnt+=(num&1);
        num>>=1;
    }
    return cnt;
}
int lowbit(int x){  //num 二进制中只保留最后一个1 如: num=20 二进制10100 返回 二进制100，也就是4
    return x&(-x);
}
int posOfOne(int num){ //num 二进制中最后一个1的位置  如: num=18 二进制10010 返回 2
    int pos=0;
    while(num){
        pos++;
        if(num&1)
            return pos;
        num>>=1;
    }
    return pos;
}
void work(int x){
    int maxstatus=1<<n;
    for(int i=0;i<maxstatus;i++){
        int nowstatus=i,t=numberOfOne(nowstatus);
        if(t!=x) continue;   //第x位女人有x个1，不是就继续找下一个数
        while(t--){
            int pos=lowbit(nowstatus);
            dp[i]=max(dp[i],dp[i-pos]+like[x][posOfOne(pos)]);
            nowstatus-=pos;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&like[i][j]);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        work(i);
    printf("%d\n",dp[(1<<n)-1]);
    return 0;
}

追问

(1>=1; x&(-x); 像这样的是什么意思呢，我没学过这样的

追答

1>=1 和num=num>>1一样，就是num左移1位 比如：num=(00011011)(二进制) num>>=1后，num=(00001101)了，相当于除2，但是比除二快很多。
x&(-x)就是两个数按位与，你可以发现这么运算后，结果就保留了x最低位的1，其他的都变成0了，针对这个性质，还有很多巧妙的应用，衍生出来一些灵巧的数据结构。

追问

中间的算法能在具体和我讲下么，不懂