UVA116 Unidirectional TSP easy DP

一道DP，题意：一张图，从第一列走到最后一列，花费最小，每次只能向右下或右上或正右方走，每一步花费为当前格子值，要求输出最小花费，并按字典序输出路线的 行变换，这里的字典序要小心，因为这个图从第一行可以直接到最后一行，反之也可以，所以相当于同样的两张图上下拼接 

思路：因为要输出路径，所以用DP做的时候得逆序来做，从最后一列找到第一列，状态转移方程很简单，边界也很好找:

dp[i][n]=mp[i][n] 即可

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

//#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin)  
//#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) 

int dp[112][112];
int mp[112][112];

int row,col;

void clear() {
	memset(dp,0,sizeof(dp));
	memset(mp,0,sizeof(mp));
}

int detal(int x) {
	x = x%row;
	if(x == 0)
		return row;
	else
		return x;
}

int main() {
	while(scanf("%d %d",&row,&col) == 2) {
		clear();
		for(int i=1;i<=row;i++) {
			for(int j=1;j<=col;j++) {
				scanf("%d",&mp[i][j]);
				if(j == col)
					dp[i][j] = mp[i][j];
			}
		}
		int ans = inf;
		int row_num = 1;
		for(int j=col-1;j>=1;j--) {
			for(int i=1;i<=row;i++) {
				dp[i][j] = min(dp[i][j+1],dp[detal(i+1)][j+1]) + mp[i][j];
				dp[i][j] = min(dp[i][j],dp[detal(i-1)][j+1] + mp[i][j]);
			}
		}
		for(int i=1;i<=row;i++) {
			if(dp[i][1] < ans) {
				ans = dp[i][1];
				row_num = i;

			}
		}
		int now_dis = ans - mp[row_num][1];
		printf("%d",row_num);
		for(int j=2;j<=col;j++) {//注意图是上下拼接的 所以字典许输出需要处理
			if(row_num == 1) {
				bool flag = false;
				for(int i=1;i<=2;i++) {
					if(dp[i][j] == now_dis) {
						printf(" %d",i);
						now_dis -= mp[i][j];
						row_num = i;
						flag = true;
						break;
					}
				}
				if(!flag) {//要按字典许输出，所以最后一行放最后处理
					printf(" %d",row);
					now_dis -= mp[row][j];
					row_num = row;
				}
			}
			else if(row_num == row) {
				bool flag = false;
				if(now_dis == dp[1][j]) {//因为字典序输出，所以先判第一行
					printf(" %d",1);
					now_dis -= mp[1][j];
					flag = true;
					row_num = 1;
				}
				if(!flag)
					for(int i=row-1;i<=row;i++) {
						if(now_dis == dp[i][j]) {
							printf(" %d",i);
							now_dis -= mp[i][j];
							row_num = i;
							break;
						}
					}
			}
			else {
				for(int i=row_num-1;i<=row_num+1;i++)
					if(now_dis == dp[i][j]) {
						printf(" %d",i);
						now_dis -= mp[i][j];
						row_num = i;
						break;
					}
			}
		}
		puts("");
		printf("%d\n",ans);
	}
	return EXIT_SUCCESS;
}

UVA116 Unidirectional TSP easy DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/19016259