蓝桥杯算法训练 金陵十三钗(dp状态压缩)------C语言—菜鸟级
2023-06-13 09:13:12 时间
/问题描述 在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人 的死亡宴会。为了不让日本人发现,自然需要一番乔装打扮。但由于天生材质的原因, 每个人和每个人之间的相似度是不同的。由于我们这是编程题,因此情况就变成了金陵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;
}
相关文章
- C语言基础:函数的定义与调用[通俗易懂]
- 2018年蓝桥杯全球变暖(简单方法求贡献)----C语言—菜鸟级
- 算法训练 格子操作(线段树)-----------C语言—菜鸟级
- C语言学习 第二章 安装编译器及运行环境
- Java高效编程之四【C语言结构的替代】详解编程语言
- Linux C语言亲子进程创建指南(linuxc创建子进程)
- C语言的优点和缺点
- 指针作为函数参数,C语言指针作为函数参数详解
- 算术运算符及算术表达式,C语言算术运算符及算术表达式详解
- Linux 下的C语言编程之旅(linux下c语言编程)
- 使用何种IDE可以更好地在Linux平台下进行C语言开发?(linuxc语言ide)
- Linux查看C语言版本的方法(linux查看c 版本)
- C语言环境下MySQL超时设置指南(c mysql设置超时)
- C语言编程开发MySQL查看器(c mysql查看器)
- C语言MySQL中常见函数掌握之道(c mysql常用函数)
- 使用C语言与MySQL删除数据表中的行(c mysql 删除行)
- C语言借助EasyX实现的生命游戏源码