本文主要是介绍UVa 116 Unidirectional TSP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题是非常基础的动态规划，类似于分阶段决策。题意是：一个M*N的数组，要求从第1列走到第N列且下一步的位置都只能是当前位置的相邻右侧，相邻右上，相邻右下三个位置。要求路径上的格子内的数字和最小。若有和相同的路径，则输出字典序最小的那一条路径。解法其实就是设置一个记忆数组，分阶段决策即可。
但是决策有从左往右和从右往左两种方式。开始我使用的从左往右的方式，这稍微麻烦一点，因为这需要把每天最优路径都求出来，然后比较字典序。可就是AC不了....不知道为什么。后来换从右到左做了，这种方式相对简单，只要在第一列中从1到M行找到最小值即可，然后以该点为路径起点输出路径即可。
#include <iostream>
#include <cstdio>
#define MAXR 10+5
#define MAXC 100+5
using namespace std;int matrix[MAXR][MAXC];
int ans[MAXR][MAXC],fa[MAXR][MAXC];
int m,n;
int main()
{while(cin>>m>>n){for(int i=1;i<=m;i++)for(int j=1;j<=n;j++) cin>>matrix[i][j];for(int i=1;i<=m;i++) ans[i][n]=matrix[i][n];for(int i=n-1;i>0;i--)for(int j=1;j<=m;j++){int t,Min;j-1==0?t=m:t=j-1;Min=j;if(ans[t][i+1]<ans[Min][i+1]) Min=t;if(ans[t][i+1]==ans[Min][i+1]&&t<Min) Min=t;//值相等，取字典较小者j+1>m?t=1:t=j+1;if(ans[t][i+1]<ans[Min][i+1]) Min=t;if(ans[t][i+1]==ans[Min][i+1]&&t<Min) Min=t;fa[j][i]=Min;//记录路径前一节点的位置ans[j][i]=matrix[j][i]+ans[Min][i+1];}int pos=1,M=ans[1][1];for(int i=1;i<=m;i++) if(ans[i][1]<M){//最小路径M=ans[i][1];pos=i;}cout<<pos;for(int i=1;i<n;i++){cout<<" "<<fa[pos][i];pos=fa[pos][i];}cout<<endl<<M<<endl;}return 0;
}这篇关于UVa 116 Unidirectional TSP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
