SWEA 4012シェフ
22552 ワード
すべての可能な状況を組み合わせて計算し、条件に合えば更新すればよい.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Solution {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static int[][] food;
static int[] numbers;
static boolean[] isSelected;
static int N, R, min = Integer.MAX_VALUE, count_combi = 0, count_combi_max;
public static void combination(int cnt, int start) { // 현재 자리에 수 뽑기.
if (cnt == N / 2) {
//System.out.println(Arrays.toString(numbers));
//System.out.println(Arrays.toString(isSelected));
if(count_combi == count_combi_max / 2)return;
count_combi++;
calc();
return;
}
// 입력받은 모든 수를 현재 자리에 넣어보기(유도파트)
for (int i = start; i < N; i++) {
isSelected[i] = true;
numbers[cnt] = i;
combination(cnt + 1, i + 1);
isSelected[i] = false;
}
}
public static int calc() {
int[] com = new int[N / 2];
int[] com_remain = new int[N / 2];
int c = 0, sumofC = 0;
int c_remain = 0, sumofC_remain = 0;
for (int i = 0; i < N; i++) {
if (isSelected[i])
com[c++] = i;
else
com_remain[c_remain++] = i;
}
for (int i = 0; i < N / 2 - 1; i++) {
for (int j = i + 1; j < N / 2; j++) {
sumofC += food[com[i]][com[j]] + food[com[j]][com[i]];
sumofC_remain += food[com_remain[i]][com_remain[j]] + food[com_remain[j]][com_remain[i]];
}
}
//System.out.println(sumofC + " " + sumofC_remain);
if (Math.abs(sumofC_remain - sumofC) < min) {
min = Math.abs(sumofC_remain - sumofC);
}
return 0;
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
R = N / 2;
food = new int[N][N];
isSelected = new boolean[N];
numbers = new int[N / 2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
food[i][j] = Integer.parseInt(st.nextToken());
}
}
count_combi = 0;
count_combi_max = 1;
for(int i = N; i > N / 2; i-- ) {
count_combi_max *= i;
}
min = Integer.MAX_VALUE;
combination(0, 0);
System.out.println("#" + tc + " " + min);
}
}
}
Reference
この問題について(SWEA 4012シェフ), 我々は、より多くの情報をここで見つけました https://velog.io/@mraz0210/SWEA4012-요리사テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol