h663: 士兵排列 (Soldiers)
Tags :
Accepted rate : 10人/19人 ( 53% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-03 00:04

Content

部隊裡 N 名士兵(編號 1~N)打算由左至右排成一列,但是有些士兵彼此 不和睦,如果在隊列中彼此相鄰,會使部隊的衝突程度增加。

舉例而言:部隊裡有 N=3 名士兵,有 2 對士兵相處的不和睦,分別為

1. 士兵 1 和士兵 2 彼此相鄰會增加 4 單位的衝突程度。

2. 士兵 2 和士兵 3 彼此相鄰會增加 6 單位的衝突程度。

如果他們的排列依序為 1、2、3,衝突程度為 4+6=10;但如果排列依序為 2、1、 3 或 3、1、2,衝突程度僅為 4,同時也為衝突程度最小的排列。

請寫程式在給定 N 名士兵和他們的關係,找出一組排列最小化衝突程度。

Input

第一行有 1 個整數 N (1≤ N ≤ 17),表示部隊裡有 N 名士兵。第 2 行到第 N+1 行每行都有 N 個非負整數,彼此皆以一個空白隔開;其中第 i+1 行從左至右數來 第 j 個數字為 Aij (0 ≤ Aij ≤ 10^2 , Aij = Aji, Aii = 0) 表示。如果士兵 i 和士兵 j 在隊伍中 相鄰,會使部隊增加 Aij 的衝突程度。

第一組 (10 分):N ≤ 3

第二組 (30 分):N ≤ 10

第三組 (60 分):無特別限制

Output

第一行請輸出一非負整數,表示最小化的衝突程度。第二行請輸出一長度為 N 的排列,表示可以最小化衝突程度的排列。如果有多組可行解請輸出字典序最小的,例如:“1 3 2 4” < “1 3 4 2”。

Sample Input #1
3
0 4 0
4 0 6
0 6 0
Sample Output #1
4
2 1 3
Sample Input #2
4
0 5 0 1
5 0 2 1
0 2 0 2
1 1 2 0
Sample Output #2
2
2 4 1 3
Sample Input #3
5
0 0 3 1 1
0 0 3 3 5
3 3 0 3 5
1 3 3 0 4
1 5 5 4 0
Sample Output #3
7
3 4 2 1 5
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (3%): 0.5s , <1K
不公開 測資點#1 (3%): 0.5s , <1K
不公開 測資點#2 (4%): 0.5s , <1K
不公開 測資點#3 (10%): 0.7s , <1K
不公開 測資點#4 (10%): 0.7s , <1K
不公開 測資點#5 (10%): 0.7s , <1K
不公開 測資點#6 (11%): 1.0s , <1K
不公開 測資點#7 (11%): 1.0s , <1K
不公開 測資點#8 (11%): 1.0s , <1K
不公開 測資點#9 (3%): 0.5s , <1K
不公開 測資點#10 (3%): 0.5s , <1K
不公開 測資點#11 (10%): 0.7s , <1K
不公開 測資點#12 (11%): 1.0s , <1M
Hint :

//如果測資不夠強或有錯誤,歡迎私信指正 謝謝

Tags:
出處:
TOI練習賽202203潛力組第2題 [管理者:
linlincaleb@... (臨末之頌)
]


ID User Problem Subject Hit Post Date
29854
r1cky (木叢欉木叢)
h663
Java 解題心得
124 2022-04-05 20:34