1390 . 鍊金術
TopCoder
Tags
Description
眼睛看不到的一個巨大趨勢，雖然我不知道那該叫做世界還是宇宙，但我跟你都是這巨大趨勢中的一個小東西也就是全中的一，但必須有這些一聚集在一起，才會行成全，這個世界依循著一個我們無法想像的巨大法則而
流動著。了解那個趨勢，並且進行分解與再築構，這就是『鍊金術』-- 鋼之鍊金術師
在這個世界的規則是這樣的：
#1有種東西叫做價值，有形也好無形也好，價值就只是個價值，越高越好。
#2任兩物質融合後，一定會有一個物質被取代，而不會產生第三種物質。
在你眼前有著n樣物質，以及兩張紙張，上面各有一個n*n 的表格
分別是：
#1當兩個物質融合後所獲得的價值是多少
#2當兩個物質融合後會是哪個物質留下(另個物質會被取代掉)
身為一個稱職的鍊金術師，你要怎樣融合使獲得的價值會最高呢?!
Input Format
包含多組測試資料，資料以EOF最為結束。(測試資料不超過10組)
每組測字資料第一行為一個數字n (1≦n≦15)，接下來有兩個n*n的表格
分別代表：
#1當兩個物質融合後所獲得的價值是多少
#2當兩個物質融合後會是哪個物質留下(另個物質會被取代掉)
Output Format
輸出可獲得的價值最高是多少。
Sample Input 1
3
1 2 3
2 2 3
3 3 3
0 0 2
0 1 2
2 2 2
5
1 7 4 0 9
7 4 8 8 2
4 8 4 5 5
0 8 5 1 7
9 2 5 7 1
0 0 2 0 4
0 1 2 3 1
2 2 2 3 2
0 3 3 3 4
4 1 2 4 4
1 2 3
2 2 3
3 3 3
0 0 2
0 1 2
2 2 2
5
1 7 4 0 9
7 4 8 8 2
4 8 4 5 5
0 8 5 1 7
9 2 5 7 1
0 0 2 0 4
0 1 2 3 1
2 2 2 3 2
0 3 3 3 4
4 1 2 4 4
Sample Output 1
6
29
29
Hints
兩物質混合沒有先後關係，固你可以假設表格都是呈現對稱的。
也就是說兩張表格都是：table[a][b]==table[b][a] 這種關係。
※2008/07/27 範例輸入修正 by hallogameboy，感謝 akira,shik。
Problem Source
原TIOJ1390 / 快樂暑假營第三次練習比賽。
Problem Setter：ggm。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 25 |
| 2 | 1 | 25 |
| 3 | 2 | 25 |
| 4 | 3 | 25 |