蓝桥杯算法训练 金陵十三钗(dp状态压缩)------C语言—菜鸟级

/问题描述
　　在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人
的死亡宴会。为了不让日本人发现，自然需要一番乔装打扮。但由于天生材质的原因，
每个人和每个人之间的相似度是不同的。由于我们这是编程题，因此情况就变成了金陵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
数据规模和约定
　　对于70%的数据，n<=10
　　对于100%的数据，n<=13
样例说明
　　最大相似度为91+92+93+73=354

思路 动态规划+状态压缩 ： 把 取 与不取 状态 为 1，0；状态 （从右向左）取 1 和 3（0101）压缩成 5
*/

#include<stdio.h>
long int n_one;
int a[14][14],dp[1<<13]={0};//记录 当前 状态最优解 如 dp[5]=26 (0101状态下 最优解为 26) 
long int ma(int a,int b)
{if(a>b)return a;
  else return b;
}

long int jl_one(int a)//记录 当前 含 1 的个数 
{ long int c=0;
   while(a)
   {   if(a%2==1)c++;
       a=a/2;
   }
   return c;
}
long int wz_one(long int a)// 找出 从左向右数最后一个 1 的位置 如 4 100 返回 3； 
{int wz=0;
     while(a)
     { wz++;
	 if(a%2==1)break;
        a=a/2;
     }
     return wz;
}
void f(int x)
{  int i,t,t2,pos;
for(i=0;i<n_one;i++)
  { t=jl_one(i);t2=i;
  if(t==x) //第x位女人有x个1，不是就继续找下一个数
         while(t--)
         {  pos=t2&(-t2);// 位运算 得从左向右最后一位 为 1 的值 如 5（101）返回 1； 
	       dp[i]=ma(dp[i],dp[i-pos]+a[x][wz_one(pos)]);//按 5（101）从右向左依此更新 
	        t2=t2-pos;
	     }
  }	
}

int main()
{
   int i,j,n,m;
   
   scanf("%ld",&n);
   for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    scanf("%d",&a[i][j]);
    n_one=1<<n;
    for(i=1;i<=n;i++)
       f(i);

  printf("%ld\n",dp[n_one-1]);// dp[n_one-1] 状态n_one-1（1111） 

return 0;
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/79767126