首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    蓝桥杯算法训练 金陵十三钗(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

    03
    领券