Unidirectional TSP
UVA116
定义:$dp[i][j]$为从第$i$行第$j$列走到最后一列的最小整数和,$Road[i][j]$为在最优方案下第$i$行第$j$列的下一步的行数(记录路径),$Map[i][j]$表示第$i$行第$j$列的数。
代码从0编号到$n-1$,而题目是1到$n$,所以会有些不一样。
初始化:1
2
3
4
5
6memset(dp, 0x0, sizeof(dp));
memset(Road, 0x0, sizeof(Road));
//从第i行第n列走到顶显然就是他本身。
for (int i = 0; i < m; ++i) {
dp[i][n - 1] = Map[i][n - 1];
}
转移方程:
由题目可知,第i行第j列可由第j+1列的i+1行、i行以及i-1行转移得到(分别对应右上,右,右下)。
因此,转移方程为:
即为$j+1$列的结果在拼接上第$j$列本身。
因为题目中的矩阵式循环的,因此方变为:
路径记录:$Road[i][j]=$当前选的行号即可
AC代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
using namespace std;
int Map[11][101], dp[11][101], Road[11][101];
int m, n;
bool Input() {
if (!(cin >> m >> n)) {
return false;
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> Map[i][j];
}
}
return true;
}
void Output(int Cow,const int&Ans) {
if (n == 1) {
cout << Cow + 1 << endl
<< Ans << endl;
return;
}
//题目编号为从1到n,所以记得加1
for (int j = 0; j < n - 1; ++j) {
cout << Cow + 1 << ' ';
Cow = Road[Cow][j];
}
cout << Cow + 1 << endl
<< Ans << endl;
return;
}
void DP() {
memset(dp, 0x0, sizeof(dp));
memset(Road, 0x0, sizeof(Road));
for (int i = 0; i < m; ++i) {
dp[i][n - 1] = Map[i][n - 1];
}
for (int j = n - 2; j >= 0; --j) {
for (int i = 0; i < m; ++i) {
//选择上一步值最小的,若值一样,选字典序较小的
auto cmp = [&j](const int&Left,const int&Right)->bool {
if (dp[Left][j + 1] == dp[Right][j + 1]) {
return Left < Right;
}
return dp[Left][j + 1] < dp[Right][j + 1];
};
//下两行对应转移方程所选择的行号
int Cow = min(((i - 1 + m) % m), i, cmp);
Cow = min(Cow, (i + 1) % m, cmp);
dp[i][j] = dp[Cow][j+1] + Map[i][j];
//路径记录
Road[i][j] = Cow;
}
}
int Ans = dp[0][0];
//枚举从第0列的每一行出发
for (int i = 0; i < m; ++i) {
Ans = min(Ans, dp[i][0]);
}
//首次出现最小值的答案是字典序最小的
for (int i = 0;; ++i) {
if (Ans == dp[i][0]) {
Output(i, Ans);
break;
}
}
}
int main() {
int Case = 0;
while (Input()) {
DP();
}
return 0;
}