開始とリンク(14889)

1.質問

質問リンク

2.解答

DFSを使用して、すべてのチームメンバーの組合せを取得します.
これは差異の最大値を求める問題です.
通常、DFSを設計する際には、
答えを呼ぶと同時に創造されたのですね.
ベースケースから答えを計算するかどうかを考えています.
この問題に対しては後者の方法が望ましい.
すべてのメンバーの組み合わせを知ってこそ、選手の能力値を計算することができるからだ.
では、再帰調ですべてのメンバーの組み合わせを求めましょう.
今では、最初のチームメンバーのグループを賢く見つけるだけで、残りはリンクチームメンバーのグループです.
スタートメンバーのグループだけ作ろう
開始チームメンバーの組合せを作成する方法は、次のとおりです.

boolean[] isStartTeam = new boolean[N];

i配列を宣言し、1人目が開始チームメンバーであるかどうかを確認します.

for (int i = startIndex; i < N; i++) {
	isStartTeam[i] = true;
	ret = Math.min(ret, min(depth + 1, i + 1));
	isStartTeam[i] = false;
}

再帰呼び出しにより、すべての起動チームメンバーが作成されます.
どのような方法で再帰的に呼び出されますか.
N=4の場合、図のように:

このように実現する
だから(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)がスタートメンバーに選ばれた.
こんな木を作るために.
上記のコードでstartIndexを用いて,現在選択されているi第2の個人(i+1)を再帰関数に渡した.
今メンバーを分けたら、グループメンバーのコンピテンシー値を開始し、グループメンバーのコンピテンシー値をリンクします.
違いが見つかれば、終わりです.

int startTeamAbility = 0; // 스타트팀 팀원들의 능력치
int linkTeamAbility = 0; // 링크팀 팀원들의 능력치
			
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		// 스타트팀 팀원들일 때
		if (isStartTeam[i] && isStartTeam[j]) {
			startTeamAbility += S[i][j];
		}
		// 링크팀 팀원들일 때
		else if (!isStartTeam[i] && !isStartTeam[j]) {
			linkTeamAbility += S[i][j];
		}
	}
}

// 두 팀의 능력치의 차이 
return Math.abs(startTeamAbility - linkTeamAbility);

まとめてみます.
1.再帰呼び出しにより、起動チームメンバーのすべての組合せを取得します.
2.ベースケースから開始チーム能力値とリンクチーム能力値の差を求める.
3.最小値を返します.
時間の複雑さ.
ケースの数はN人(N/2)人から抽出した数ですから.
N!/(2 x (N/2)!) 犬がいます.
いずれの場合もチームコンピテンシー値を計算するロジックにはN^2が必要です
合計(N^2 xN!)/(2 x (N/2)!) .

3.完全なコード

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N;
	static int[][] S;
	static boolean[] isStartTeam;
	
	static int min(int depth, int startIndex) {
		// 2. 기저사례에서 스타트팀 능력치와 링크팀 능력치의 차이를 구합니다.
		if (depth == N / 2) {
			int startTeamAbility = 0; // 스타트팀 팀원들의 능력치
			int linkTeamAbility = 0; // 링크팀 팀원들의 능력치
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					// 스타트팀 팀원들일 때
					if (isStartTeam[i] && isStartTeam[j]) {
						startTeamAbility += S[i][j];
					}
					// 링크팀 팀원들일 때
					else if (!isStartTeam[i] && !isStartTeam[j]) {
						linkTeamAbility += S[i][j];
					}
				}
			}
			
			// 두 팀의 능력치의 차이 
			return Math.abs(startTeamAbility - linkTeamAbility);
		}
		
		int ret = 987654321;
		
		// 1. 재귀호출로 스타트팀 팀원의 모든 조합을 구합니다.
		for (int i = startIndex; i < N; i++) {
			isStartTeam[i] = true;
			ret = Math.min(ret, min(depth + 1, i + 1));
			isStartTeam[i] = false;
		}
		
		// 3. 가장 작은 값을 리턴합니다.
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		S = new int[N][N];
		isStartTeam = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				S[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		bw.write(min(0, 0) + "");
		bw.close();
	}
}

再帰呼び出しは、最小の例で画像を描くことに慣れています.