alan23273850 的刷題筆記
c100: 00116 - Unidirectional TSP
Tags: dp
出處：https://zerojudge.tw/ShowProblem?problemid=c100
提交：https://zerojudge.tw/Submissions?problemid=c100&account=allllllan123456
問題：給定一張 $m\in[1,10]$ 橫列、$n\in[1,100]$ 直行的地圖方陣，每個元都是一個 int 整數，現在要從第一直行選一個起點開始向右走每次行走可以選擇右上方、正右方、右下方三個方向，並且這張地圖可以像遊戲一樣上下環繞，最上面一列的右上方會自動傳送到右邊的最下方一列，最下面一列的右下方會自動傳送到右邊最上方一列，走到最右一行的時候停止，定義此時的路徑重量為從頭到尾走過的方陣元素總和。請問以第一行的哪一個元作為起點，過程中如何選擇方向，走到最後一行的時候會有最大的路徑重量？其值為何？如果有多組解，那麼在每一行之中請盡量選擇列號最小的方向。
解法：也是用經典 DP 就可以解決的問題，要計算以任何一行的任何一個元作為起點，走到最後一行的最小重量，可以從其右上方、正右方、右下方的三個子問題計算結果來決定，我們可以挑一個最小的作為下一步的方向，再加上自己這個元素就形成自己的答案。因為每個子問題都會被考慮到，這題就可以用 bottom up 的 DP 來解，從最右邊一行開始填表 (此時的答案剛好就是自己那個元素)，依序往左一行填表，直到第一行完畢。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int m, n, arr[10][100], dp[10][100], nextI[10][99];
6 while (cin >> m >> n) {
7 for (int i=0; i<m; i++) for (int j=0; j<n; j++) cin >> arr[i][j];
8 for (int i=0; i<m; i++) dp[i][n-1] = arr[i][n-1];
9 for (int j=n-2; j>=0; j--)
10 for (int i=0; i<m; i++) {
11 int min = INT_MAX, indices[] = {(i+m-1) % m, i, (i+1) % m};
12 sort(indices, indices+3);
13 for (auto i2: indices)
14 if (dp[i2][j+1] < min)
15 min = dp[i2][j+1], nextI[i][j] = i2;
16 dp[i][j] = arr[i][j] + min;
17 }
18 int ans = INT_MAX, minI = INT_MAX;
19 for (int i=0; i<m; i++)
20 if (dp[i][0] < ans)
21 ans = dp[i][0], minI = i;
22 cout << minI + 1;
23 for (int j=0; j<n-1; j++)
24 minI = nextI[minI][j], cout << ' ' << minI + 1;
25 cout << '\n' << ans << '\n';
26 }
27 return 0;
28}