[白俊]14889号:スタートとリンク/PTython/ロングホッケー
開始とリンク
質問する
今日はスタート地点を走る人が集まってサッカーをします.サッカーは平日の午後に行われ、義務参加でもない.サッカーをするために集まったのは全部でN人で、不思議なことにNは偶数です.今はN/2人からなるスタートチームとリンクチームに分けます.
BOJを運営する会社のように、1からNの番号を割り当て、以下の能力値を調べた.コンピテンシー値SijS{ij}Sijは、i番とj番が同じチームに属する場合、チームに増加するコンピテンシー値です.チームのコンピテンシー値は、チーム内のすべてのペアのコンピテンシー値SijS{ij}Sijの和です.SijS{ij}SijがSjiS{ji}Sjiと異なる可能性があり、i号とj号が同じチームに属する場合、チームに増加する能力値はSijS{ij}SijとSjiS{ji}Sjiである.
N=4,Sは以下のようになります.
たとえば、1、2番が先頭チーム、3、4番がリンクチームの場合、2つのチームの能力値は次のようになります.
サッカーを面白くするために、スタートチームの能力値とリンクチームの能力値の差を最小限に抑えたい.上記の例のように、1、4が開始グループ、2、3がリンクグループの場合、開始グループのコンピテンシー値は6、リンクグループのコンピテンシー値は6、差異は0であり、この値は最小である.
入力
第1行はN(4≦N≦20,Nは偶数)を与える.2行目からN行Sを与える.各行はN個の数字で構成され,i行のj号はSijS{ij}Sijである.SiiS{i}Siiは常に0であり、残りのSijS{ij}Sijは1以上100以下の整数である.
しゅつりょく
最初の行は、開始グループとリンクグループのコンピテンシー値の差の最大値を出力します.
解答方法
BrootForsアルゴリズムを使用して、開始チームとリンクチームを区別できるすべての状況の数を探索します.チームを区別するためにアクセスリストを作成し、True、Falseとして保存します.
import sys
sys.setrecursionlimit(100001)
input = sys.stdin.readline
n = int(input())
s = []
for _ in range(n):
s.append(list(map(int, input().split())))
visited = [False] * n # start와 link팀을 표시하기 위함
result = 1e9
def solve(idx, cnt):
global result
if cnt == n / 2: # 팀을 모두 나누었으면
start, link = 0, 0
for i in range(n):
for j in range(n):
if visited[i] and visited[j]: # visited가 True이면 start팀으로
start += s[i][j]
elif not visited[i] and not visited[j]: # False이면 link팀으로
link += s[i][j]
result = min(result, abs(start - link)) # 차이의 최솟값 갱신
return
# dfs로 팀원 분배
for i in range(idx, n):
if not visited[i]:
visited[i] = True
solve(i + 1, cnt + 1)
visited[i] = False
solve(0, 0)
print(result)Reference
この問題について([白俊]14889号:スタートとリンク/PTython/ロングホッケー), 我々は、より多くの情報をここで見つけました https://velog.io/@dhelee/백준-14889번-스타트와-링크-Python-브루트-포스テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol