Unidirectional TSP UVA

Unidirectional TSP UVA - 116（dp）

本文主要是介绍Unidirectional TSP UVA - 116（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以前试着弄紫书上的dp不过都浅尝而止，没有独立思考一道比较难的dp题目。没想到今天竟然a了一道（不过这道也不算很难，主要还是我太菜）……
不容易啊orz…

思路

这道题在保证路径和最小的情况下还要保证字典序最小。我是从左向右递推的，递推的过程主要做了一个决策，是选择右y上右还是右下，首先肯定要选最小的了，但要保证字典序最小就不容易了，因为这道题第一层的上一层是最后一层orz。我的做法是保存到结构体中再sort一下。打印路径的也是一个细节～

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;const int maxr = 15;
const int maxc = 120;struct point {int y;int x;point(int y = 0, int x = 0) : y (y) , x(x) {}
};point nex[maxr][maxc];int num[maxr][maxc];
int dp[maxr][maxc];bool cmp(point a, point b) {return a.y < b.y;
};
int n, m;int main()
{//freopen("input.txt", "r", stdin);while(~scanf("%d%d", &n, &m)) {memset(dp, 0, sizeof(dp));for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {scanf("%d", &num[i][j]);}}for(int i = 0; i < n; i++) {dp[i][m-1] = num[i][m-1];}for(int j = m-2; j >= 0; j--) {for(int i = 0; i < n; i++) {point po[3] = {point((i-1+n)%n,j+1), point(i, j+1), point((i + 1)%n, j+1)};sort(po, po + 3, cmp);int k, minn = INT_MAX;for(int t = 0; t < 3; t++) {if (dp[po[t].y][po[t].x] < minn) {k = t;minn = dp[po[t].y][po[t].x];}}nex[i][j] = po[k];dp[i][j] = num[i][j] + minn;}}int minans = INT_MAX;int beg;for(int i = 0; i < n; i++) {if (dp[i][0] < minans) {minans = dp[i][0];beg = i;}}printf("%d", beg+1);point t = nex[beg][0];for(int i = 1; i < m; i++) {printf(" %d", t.y+1);t = nex[t.y][t.x];}printf("\n");printf("%d\n", minans);}return 0;
}