UVA 116——Unidirectional TSP

深藏阁楼爱情的钟 2022-08-17 14:09 97阅读 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 条评论，97人围观）

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

相关阅读

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

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

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

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

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

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

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

相关 python系列教程116

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

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

相关 UVA 116——Unidirectional TSP

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

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

相关 tsp问题——遗传算法解决

TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！。可以形象地把解空间看成是一个无

小鱼儿/ 2022年08月04日 08:29/ 0 赞/ 151 阅读

相关 uva 116 数塔动态规划

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

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

相关 UVA 116(单向TSP)

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

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

相关动态规划求解TSP圈

求解思路：动态规划的方法的最大难点就在于初始变量的确定，选择合适的初始变量才能更好的运用动态规划的方式解决问题。我在这里定义的变量就是d(i,S),

痛定思痛。/ 2022年04月25日 09:30/ 0 赞/ 189 阅读

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

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

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