首页 > 试题广场 >

旅行Ⅱ

[编程题]旅行Ⅱ
  • 热度指数：754 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛妹出去旅行啦，她准备去个城市旅行，去每个城市的开销是元。但是牛妹有强迫症，她想在去y城市之前先旅游x城市，于是牛妹列出了这些限制条件List。并且牛妹很节约，她只有元，她想知道她最多能到多少个城市去旅游。
示例1

输入

3,10,[3,7,8],[(1,2)]

输出

2

说明

先去1号城市再去2号城市，花费为 3+7=10

备注:
A[0]代表1号城市的开销
A[1]代表2号城市的开销,以此类推



算法知识视频讲解
开通博客
头像 Maokt
发表于 2021-08-07 18:05:53
算法思想一：递归+记忆化递归 解题思路： 可以对种状态利用二进制掩码形式逐一对其递归进行搜索，每次查看经费和前后续关系。搜索函数中为当前的状态数，为当前最大这段序列可访问的最大城市数，递归的时候减小经费，改变与即可进入子问题。为了防止递归处理的问题太大，可以用数组dp记录所有的前面计算过 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-08 12:52:43
题目描述牛妹出去旅行啦，她准备去N个城市旅行，去每个城市的开销是Ai元。但是牛妹有强迫症，她想在去y城市之前先旅游x城市，于是牛妹列出了这些限制条件List。并且牛妹很节约，她只有V元，她想知道她最多能到多少个城市去旅游。 方法一：递归法 求解思路对于求解本题目，我们首先将牛妹去过的城市用一个二进制 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-08-07 13:41:28
题意整理 给定N个城市，以及每个城市的开销。 一个前置城市数组，即去y城市之前必须先去x城市。 求牛妹用V元最多能去多少个城市旅游。 方法一（记忆化递归） 1.解题思路 前置知识：假设有N个城市，每个城市的编号是，牛妹去了哪几个城市可以用一个N位二进制编码mask来表示，mask中对应位是1，则 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-03 13:57:40
思路： 题目的主要信息： 一个N个城市，A数组中记录的是访问每个城市所需的花费，V是初始所有的总预算 如果同时访问了两个城市，需要满足List中Point记录的先后顺序 求满足预算条件下，最多访问的城市数 方法一：暴力法（超时）具体做法：利用next_permutation函数对1-N个城市进行 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Tag_Kausal
发表于 2020-02-07 11:59:38
做法1：AC数据范围较小，考虑状压dp，表示构成集合i的最小花费，用二进制状压表示。所以我们考虑先枚举集合，再枚举集合外的点，去验证这个点能否加入这个集合。总的时间复杂度为，空间复杂度为。 class Solution { public: int Travel(int N, int V, i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 ls.joshua
发表于 2020-04-08 20:36:51
joshua分享：从第一个节点开始依次进行深度搜索即可，每一步的搜索都要判断是否合法，需要满足下面的几个规则：1. 当前节点没有走过；2. 当前费用足够当前节点的消费；3. 当前节点的所有前驱节点都已经走过； /** * struct Point { * int x; * int y; 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 位运算
难度：
1条回答 5819浏览

热门推荐

通过挑战的用户

查看代码

相关试题

旅行Ⅱ

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号