UVA 116——Unidirectional TSP

深藏阁楼爱情的钟 2022-08-17 14:09 169阅读 0赞

题意：给定一个n\*m的矩阵，从第一列任意位置向右，右下，右上走一格，可以循环，要求经过的数字的和最小。

思路：记忆化搜索。每次有三个状态，从这三个状态中选择出最优的一个，然后状态累加，保存路径。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=11;
    const int M=105;
    #define ft(i,s,t) for (int i=s;i<=t;i++)
    #define frt(i,t,s) for (int i=t;i>=s;i--)
    int g[N][M],s[N][M];
    
    int main()
    {
        int n,m,t,tt;
        while (~scanf("%d %d",&n,&m))
        {
            ft(i,0,n-1) ft(j,0,m-1) scanf("%d",&g[i][j]);
    
            frt(j,m-2,0) ft(i,0,n-1)
            {
                int bt=(i+n-1)%n;
                if (g[i][j+1]<g[bt][j+1]||g[i][j+1]==g[bt][j+1]&&bt>i) bt=i; //右上和直走的最优解
                int t=(i+1)%n;
                if (g[t][j+1]<g[bt][j+1]||g[t][j+1]==g[bt][j+1]&&bt>t) bt=t;//右下和全部
    
                g[i][j]+=g[bt][j+1];s[i][j]=bt; //状态记忆和保存路径
            }
    
            int p=n-1;
            frt(i,n-2,0) if (g[p][0]>=g[i][0]) p=i;
            int ans=g[p][0];
            ft(i,0,m-2)
            {
                printf("%d ",p+1);
                p=s[p][i];
            }
    
            printf("%d\n%d\n",p+1,ans);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 tsp的理论和实践(10)tsp系列暂停一下

目前tsp系列已经写了9篇了, 没有哪一篇的阅读量超过100, 对比一下, 随便写的\[面试\]和\[简历\]这两篇, 6分钟阅读量就200了. 最关键的是: 一个留言...

心已赠人/ 2024年04月17日 13:56/ 0 赞/ 57 阅读

相关遗传算法解决TSP问题

一、求解问题概述 1.1 TSP问题 TSP问题是指旅行商问题（Traveling Salesman Problem）。在TSP问题中，假设有一名旅行商要在给定的一

向右看齐/ 2024年03月16日 16:23/ 0 赞/ 29 阅读

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

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

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

相关 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 赞/ 46 阅读

相关 python系列教程116

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

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

相关 UVA 116——Unidirectional TSP

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

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

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

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

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

相关 uva 116 数塔动态规划

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

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

相关 UVA 116(单向TSP)

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

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

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

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

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