h663.
士兵排列 (Soldiers)
內容
部隊裡 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 名士兵和他們的關係，找出一組排列最小化衝突程度。
輸入說明
第一行有 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 分)：無特別限制
輸出說明
第一行請輸出一非負整數，表示最小化的衝突程度。第二行請輸出一長度為 N 的排列，表示可以最小化衝突程度的排列。如果有多組可行解請輸出字典序最小的，例如：“1 3 2 4” < “1 3 4 2”。
範例輸入
#1
3 0 4 0 4 0 6 0 6 0
範例輸出
#1
4 2 1 3
範例輸入
#2
4 0 5 0 1 5 0 2 1 0 2 0 2 1 1 2 0
範例輸出
#2
2 2 4 1 3
範例輸入
#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
範例輸出
#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
不公開 測資點#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
提示 ：
//如果測資不夠強或有錯誤，歡迎私信指正 謝謝
標籤:
出處:
TOI練習賽202203潛力組第2題
[管理者：
linlincaleb@
...
(臨末之頌)
]