UVA 116 Unidirectional TSP(dp)

比眉伴天荒 2024-02-17 19:29 42阅读 0赞

分析：本题中每一列就是一个阶段，每个阶段有三种决策；状态方程dp\[i\]\[j\]=min(dp\[i-1\]\[j+1\],dp\[i\]\[j+1\],dp\[i+1\]\[j+1\]);dp(i,j)表示当前阶段到最后一列的最小消耗。

路径记录：用next1\[\]\[\]来保存下一列行号。

AC代码：

#include<cstdio>
    #include<algorithm>
    #define INF 2147483647 
    using namespace std;
    int dp[12][102];
    int a[12][102];
    int next1[12][102];
    int main(){
    	int n,m;
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i=0;i<n;i++)
    		  for(int j=0;j<m;j++)
    		   scanf("%d",&a[i][j]);
    	    int T=INF,first=0;
    	    for(int j=m-1;j>=0;j--){
    	    	for(int i=0;i<n;i++){
    	    		if(j==m-1)dp[i][j]=a[i][j];
    	    		else {
    	    			int rows[]={i,i-1,i+1};
    	    			if(i==0)rows[1]=n-1;
    	    			if(i==n-1)rows[2]=0;
    	    			sort(rows,rows+3);
    	    			dp[i][j]=INF;
    	    			for(int k=0;k<3;k++){
    	    				int tmp=a[i][j]+dp[rows[k]][j+1];
    	    				if(tmp<dp[i][j]){
    	    					dp[i][j]=tmp;
    	    					next1[i][j]=rows[k];
    						}
    					}
    				}
    				if(j==0 &&T >dp[i][j]){
    							T=dp[i][j];
    							first=i;
    						}
    			}
    		}
    		
    		printf("%d",first+1);
    		int i=first;
    		for(int j=0;j<m-1;j++){
    			printf(" %d",next1[i][j]+1); 
    			i=next1[i][j];
    		}
    		printf("\n%d\n",T);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读

相关 116.排行榜处理-案例

--图书销售数据表 CREATE TABLE tb( Books nvarchar(30), --书名 Date datetime, -

落日映苍穹つ/ 2024年02月19日 19:02/ 0 赞/ 48 阅读

相关 UVA 116 Unidirectional TSP(dp)

分析：本题中每一列就是一个阶段，每个阶段有三种决策；状态方程dp\[i\]\[j\]=min(dp\[i-1\]\[j+1\],dp\[i\]\[j+1\],dp\[i+1\]

比眉伴天荒/ 2024年02月17日 19:29/ 0 赞/ 43 阅读

相关 python系列教程116

朋友们，如需转载请标明出处：[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow] 声明

电玩女神/ 2022年08月28日 06:48/ 0 赞/ 196 阅读

相关 NYOJ 116 士兵杀敌（二）

士兵杀敌（二）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 5 描述南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

心已赠人/ 2022年08月25日 05:17/ 0 赞/ 176 阅读

相关 UVA 116——Unidirectional TSP

题意：给定一个n\m的矩阵，从第一列任意位置向右，右下，右上走一格，可以循环，要求经过的数字的和最小。思路：记忆化搜索。每次有三个状态，从这三个状态中选择出最优的

深藏阁楼爱情的钟/ 2022年08月17日 14:09/ 0 赞/ 166 阅读

相关 uva 116 Unidirectional TSP【数塔+打印路径】

题目： uva 116Unidirectional TSP 题意：给出一个矩阵，当前的格子值为后面三个方向的格子最小值和当前的和，就第一列的最小值并打印路径（相同则

冷不防/ 2022年08月12日 03:29/ 0 赞/ 15 阅读

相关 uva 116 数塔动态规划

横着的数塔，从左往右走，可以走右上，右，右下三个方向，最后一行往右下走可以穿越到第一行，第一行往右上走可以穿越到最后一行。最后要求输出走的路径以及路径和的最小值，

亦凉/ 2022年08月03日 13:41/ 0 赞/ 216 阅读

相关 nyoj--116--士兵杀敌（二）

士兵杀敌（二）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 5 描述南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的

浅浅的花香味﹌/ 2022年06月10日 05:25/ 0 赞/ 180 阅读

相关 UVA 116(单向TSP)

题目来源:[点击打开链接][Link 1] 题目题意:题目给我们一个m\n的数阵，我们从第一列的任何位置出发，每次只能向右，右上，右下前进，到达最后一列，且矩阵式环形的，求经

爱被打了一巴掌/ 2022年06月07日 02:40/ 0 赞/ 173 阅读

相关 UVa116 Unidirectional TSP 多段图的最短路

题意：给定一个n\m的矩阵，要求从第一列的任何一行出发，每次沿右或右下或右上到达后面一列，最后到第m列任何一行整个路程的最小值，并且要求是字典序最小的。分析：阶段很明

向右看齐/ 2021年12月19日 02:25/ 0 赞/ 209 阅读