phpcmsv9 网站搬家/优化服务公司
UVa116 Unidirectional TSP
题意：给定一个n*m的矩阵，要求从第一列的任何一行出发，每次沿右或右下或右上到达后面一列，最后到第m列任何一行整个路程的最小值，并且要求是字典序最小的。
分析：阶段很明显，一列便是一个阶段，在一列的每一个状态都有3种决策，右，右下，右上，直接更新最小值就行了。注意题目要求字典序最小，刚开始是顺推，定义dp[i][j]为在第i行第j列时走过的路程的最小值，但是发现后面难以求取字典序最小的方案，路径根本不好记录，所以WA了….就算记录了路径，也要进行逆向打印，不是很方便，最后改用逆推便解决了这个问题。
对于这种在规划最优值的同时还要求取字典序最小方案的题，选择合适的递推顺序，利用数组直接记录路径省去循环都会是可行的选择，紫书上面还是讲得挺好的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;int mat[30][110], dp[30][110], path[30][110];
int n, m;
int main()
{while (~scanf("%d %d", &n, &m)){for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) scanf("%d", mat[i]+j);memset(dp, INF, sizeof(dp));for (int i = 1; i <= n; i++) dp[i][m] = mat[i][m];for (int j = m; j > 1; j--){for (int i = 1; i <= n; i++){int row[3] = {i-1, i, i+1};if (i == 1) row[0] = n;if (i == n) row[2] = 1;sort(row, row+3);for (int x = 0; x < 3; x++){int tmp = dp[i][j]+mat[row[x]][j-1];if (tmp < dp[row[x]][j-1]){dp[row[x]][j-1] = tmp;path[row[x]][j-1] = i;}}}}int cost = INF, r;for (int i = 1; i <= n; i++)if (cost > dp[i][1]) r = i, cost = dp[i][1];printf("%d", r);for(int i = path[r][1], j = 1; j < m; j++, i = path[i][j]) printf(" %d", i);printf("\n%d\n", cost);}return 0;
}