专栏首页AI那点小事算法提高 金陵十三钗

算法提高 金陵十三钗

金陵十三钗   本题难度:难   本题占分比例:5% 问题描述   在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人的死亡宴会。为了不让日本人发现,自然需要一番乔装打扮。但由于天生材质的原因,每个人和每个人之间的相似度是不同的。由于我们这是编程题,因此情况就变成了金陵n钗。给出n个女人和n个学生的相似度矩阵,求她们之间的匹配所能获得的最大相似度。   所谓相似度矩阵是一个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


代码:

import java.util.Scanner;

/*
 * 8皇后的变种
 */
public class Main {
    static int N;
    static int[][] num;
    static int[] b;
    static int sum = 0;

    public static void dfs(int t){
        if ( t == N){
            int sum1 = 0;
            for ( int i = 0 ; i < N ; i++){
                sum1 += num[i][b[i]];
            }
            sum = Math.max(sum, sum1);
            return;
        }else{
            //第cur个人替代第i个人  
            for ( int i = 0 ; i < N ; i++){
                boolean flag = true;
                int j;
                for ( j = 0 ; j < t ; j++){
                    //第i个人已经被替代了
                    if( b[j] == i){
                        flag = false;
                        break;
                    }
                }
                if ( flag == true){
                    b[j] = i;
                    dfs(t+1);
                }
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        num = new int[N][N];
        b = new int[N];
        for ( int i = 0 ; i < N ; i++){
            for (int j = 0 ; j < N ; j++){
                num[i][j] = in.nextInt();
            }
        }
        dfs(0);
        System.out.println(sum);

        in.close();
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事
  • 历届试题 最大子阵

    问题描述   给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。

    AI那点小事
  • 挑战程序竞赛系列(4):2.1深度优先搜索

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • HDUOJ --2544最短路(基础)

    输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛...

    Gxjun
  • 房上的猫:数组插入算法等难点专开

    一:查找算法 public class Aini { public static void main(String[] args) { ...

    房上的猫
  • Java常用排序算法/程序员必须掌握的8大排序算法

    1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)

    哲洛不闹
  • 古典密码加密解密之多表代换

    多表代换密码首先将明文M 分为由n 个字母组成的分组, , … ,对每个分组的加密为 ≡ + ( ), = , , … 其中,(A,B)是密钥,A 是 ...

    张泽旭
  • HDU 4786Fibonacci Tree(最小生成树)

    Problem Description   Coach Pang is interested in Fibonacci numbers while Un...

    attack
  • 对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

    本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的(保证了这个点的距离就是最短路),如果有负边权,当前找到的就不一定是最近的了。

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券