블 루 브리지 컵알고리즘 증가금릉 13 비녀

4005 단어 알고리즘
금릉 13 비녀 본제 난이도: 어 려 운 본제 가 차지 하 는 비율: 5% 문 제 는 영화 '금릉 13 비녀' 에서 12 명의 진 화 이 허 의 여자 가 12 명의 여학생 을 대신 해 일본 인의 사망 연회 에 가 는 것 을 묘사 했다.일본 인 들 에 게 들 키 지 않 기 위해 서 는 당연히 변장 이 필요 하 다.하지만 타고 난 소재 때문에 사람마다 싱크로 율 이 다르다.우 리 는 프로 그래 밍 문제 이기 때문에 상황 은 금릉 n 비녀 가 되 었 다.n 명의 여자 와 n 명의 학생 의 싱크로 율 행렬 을 제시 하고 그들 사이 의 일치 가 얻 을 수 있 는 최대 싱크로 율 을 구한다.싱크로 율 행렬 이란 n * n 의 2 차원 배열 like [i] [j] 이다.그 중에서 i, j 는 각각 여자 의 번호 와 학생 의 번호 로 모두 0 에서 n - 1 번호 이다.like [i] [j] 는 0 에서 100 의 정수 로 i 번 째 여자 와 j 번 째 학생 의 싱크로 율 을 나타 낸다. 수치 가 클 수록 싱크로 율 이 크다. 예 를 들 어 0 은 전혀 비슷 하지 않다 는 뜻 이 고 100 은 100% 같다 는 뜻 이다.모든 여 자 는 자신 이 대신 할 여학생 을 찾 아야 한다.결국 양쪽 을 일일이 맞 춰 하나의 매 칭 을 이 루어 야 한다.각 여자 와 여학생 간 의 싱크로 율 을 최대 로 맞 추 는 방안 을 찾 으 십시오.입력 형식 첫 번 째 줄 의 정수 n 은 n 개의 진 화 이 허 여자 와 n 명의 여학생 이 다음 n 줄 에 싱크로 율 을 나타 내 고 n 줄 마다 0 에서 100 의 정 수 를 나타 내 며 2 차원 행렬 의 n 행 n 열 에 순서대로 대응 합 니 다.출력 형식 은 한 줄, 한 정수 로 얻 을 수 있 는 최대 싱크로 율 을 표시 합 니 다.샘플 입력 4 97 91 68 14 33 92 36 32 98 73 7 17 82 사례 수출 354 데이터 규모 와 약정 70% 의 데이터, n < = 10 대 100% 의 데이터, n < = 13 사례 설명 최대 싱크로 율 91 + 92 + 98 + 73 = 354
import java.util.Scanner;

/** * @author   * */
public class Main {
    private static int n;
    private static int[][] mat;
    private static int max=Integer.MIN_VALUE;

    /** * @param args */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        mat=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                mat[i][j]=sc.nextInt();
            }
        }
        int sum=0;
        boolean[] hasSelected=new boolean[n];
        fun(0,sum,hasSelected);
        System.out.println(max);
    }

    private static void fun(int index,int sum,boolean[] hasSelected){
        if(index==n){
            if(sum>max){
                max=sum;
                return;
            }
        }
        for(int i=0;i<n;i++){
            if(!hasSelected[i]){
                hasSelected[i]=true;
                fun(index+1,sum+mat[index][i],hasSelected);
                hasSelected[i]=false;
            }
        }
    }

}

좋은 웹페이지 즐겨찾기