题目:售货员的难题(状压dp)

售货员的难题

  • 题目描述
  • 输入输出格式
    • 输入格式:
    • 输出格式:
  • 输入输出样例
    • 输入样例#1:
    • 输出样例#1:
  • 思路
  • AC代码:

题目描述

某乡有n个村庄( 1 < n <= 16 ),有一个售货员,他要到各个村庄去售货,各村庄之间的路程s(0 < s < 1000)是已知的,且A村到B村与B村到A村的路大多不同。为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为1,他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

输入输出格式

输入格式:

第一行一个数n表示村庄数
接下来是一个n×n的矩阵,表示各村庄之间的路程。

输出格式:

最短的路程。

输入输出样例

输入样例#1:

3
0 2 1
1 0 2
2 1 0 

输出样例#1:

3

思路

这是一道状压dp,所以做这道题之前需要先知道一些关于状态压缩的基本概念。简单来说,就是在一般的题目里,一个数组即可保存状态。但是有这样的一些题 目,它们具有DP问题的特性,但是状态中所包含的信息过多,如果要用数组来保存状态的话需要四维以上的数组。于是,我们就需要通过状态压缩来保存状态,而 使用状态压缩来保存状态的DP就叫做状态压缩DP。例如这道售货员难题,若有n 个村庄,想要表示是否经过每个村庄的状态,则需要使用n维数组,而采取状态压缩,往往利用二进制的整数来简单的表示状态,如 0101 0101 0101,则表示经过了 1 1 1 3 3 3号村庄,没有经过 2 2 2 4 4 4号村庄。

我先介绍一下位运算相关的知识:
在这里插入图片描述

还有几种在状压dp中常见的应用如下:
1.判断一个数字x二进制下第i位是不是等于1。

方法:if ( ( ( 1 << ( i - 1 ) ) & x ) > 0)

将1左移i-1位,相当于制造了一个只有第i位上是1,其他位上都是0的二进制数。然后与x做与运算,如果结果>0,说明x第i位上是1,反之则是0。

2.将一个数字x二进制下第i位更改成1。

方法:x = x | ( 1<<(i-1) )

证明方法与1类似,此处不再重复证明。

3.把一个数字二进制下最靠右的第一个1去掉。

方法:x=x&(x-1)

回过头来看这道题,n<20,使用状态压缩将会很方便,dp[i][j]表示从起始点到i号点在j状态下花费的最短路程,例如n=3,dp[3][3],即表示从起始点到3号点,在011,也就是经过了1号点和2号点的情况的最短路程。
详细的状态方程可以见代码,再填出dp表格后,比较不同的点在经过所有点后到起始点的路程,便可以得到答案

AC代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int map[21][21];
int dp[21][40000]; 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>map[i][j];
		}
	}
	memset(dp,64,sizeof(dp));
	dp[1][1]=0;
	for(int i=0;i<=(1<<n);i++)//枚举路线
	{
		for(int j=1;j<=n;j++)//枚举村庄 
		{
			if(((1<<(j-1))&i)==0)//如果第i号村庄没去过第j号村庄就往下 
			{
				for(int q=1;q<=n;q++)//枚举村庄 
				{
					if(1<<(q-1)&i)//如果第i号村庄去了第q号村庄就往下 
					{
						dp[j][1<<j-1|i]=min(dp[j][1<<j-1|i],dp[q][i]+map[q][j]);
						//dp[j][1<<j-1|i]为:经过i号村庄去j号村庄
						//dp[q][i]+map[q][j]为:经过i号村庄去q号村庄,再从q号村庄去j号村庄
						//类似于Floyd
					}
					
				}
			}
		}
	}
	int ans=9999999;
	for(int i=2;i<=n;i++)
	{
		ans=min(ans,dp[i][(1<<n)-1]+map[i][1]);
		//判断从1号村庄去哪一号村庄可以更快的跑完
	}
	cout<<ans<<endl;
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/77645.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

每天一道leetcode:433. 最小基因变化(图论中等广度优先遍历)

今日份题目&#xff1a; 基因序列可以表示为一条由 8 个字符组成的字符串&#xff0c;其中每个字符都是 A、C、G 和 T 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如&#xff0c;&quo…

数据结构----哈夫曼树

这里写目录标题 基本概念引子基本概念各种路径长度各种带权路径长度结点的带权路径长度树的带权路径长度哈夫曼树 哈夫曼树的构造理论基础构造思想总结 哈夫曼树的实现哈夫曼编码前缀编码哈夫曼编码的思想案例代码实现 编码与解码 基本概念 引子 哈夫曼树就是寻找构造最优二叉…

k8s RBAC授权普通系统用户对namespace访问权限

背景&#xff1a;最近遇到一个问题&#xff0c;那就是需要给别人共享一下 Kubernetes 的某个资源的使用和访问权限&#xff0c;这个仅仅存在于某个 namespace 下&#xff0c;但是我又不能把管理员权限全都给它&#xff0c;我想只给他授予这一个 Namespace 下的权限&#xff0c;…

OpenShift 4 - 基于 MinIO 安装 Red Hat Quay 镜像仓库

《OpenShift / RHEL / DevSecOps 汇总目录》 说明&#xff1a;本文已经在 OpenShift 4.13 Quay 3.9 的环境中验证 本文适合在单机 OpenShift 环境安装 Red Hat Quay 镜像仓库。 另外《OpenShift 4 - 安装 ODF 并部署红帽 Quay (1 Worker)》也可以在单节点部署。 而《OpenShif…

分布式版本控制系统(一)

分布式版本控制系统(一) 目录 分布式版本控制系统(一) 1、Git、Github、Gitlab 的区别2、Git 与 SVN 区别3、Git工作流程4、Git基本概念5、Git 客户端安装使用 5.1 git-server安装配置5.2 git-client配置免密登录git服务器5.3 文本编辑器5.4 差异分析工具5.5 查看配置信息5.6 常…

基于IMX6ULLmini的linux裸机开发系列一:汇编点亮LED

思来想去还是决定记录一下点灯&#xff0c;毕竟万物皆点灯嘛 编程步骤 使能GPIO时钟 设置引脚复用为GPIO 设置引脚属性(上下拉、速率、驱动能力) 控制GPIO引脚输出高低电平 使能GPIO时钟 其实和32差不多 先找到控制LED灯的引脚&#xff0c;也就是原理图 文件名 C:/Us…

动态内存分配及管理——C语言

目录 一、为什么存在动态内存分配 二、动态内存函数介绍 2.1 malloc 2.2 free 2.3 calloc 2.4 realloc 三、常见的动态内存错误 3.1 对NULL指针的解引用操作 3.2 对动态开辟空间的越界访问 3.3 对非动态开辟内存使用free释放 3.4 使用free释放一块动态开辟内存的一部…

Vue3 Vuex状态管理多组件传递数据简单应用

去官网学习→安装 | Vuex cd 项目 安装 Vuex&#xff1a; npm install --save vuex 或着 创建项目时勾选Vuex vue create vue-demo ? Please pick a preset: Manually select features ? Check the features needed for your project: (Press <space> to se…

Web3 solidity订单池操作

前面一篇文章因为一些原因 被设为了进自己可见 需要的朋友可以私信我 之前 我们编写的程序上来看 交易所无非是一个代币的托管上 只是它会更加专业 本文 我们继续来看交易所的一个功能 叫游泳池 例如 我们 100grToken 兑换 1ETH 前提 我们的代币已经能被估值了 例如 你想用人…

【JVM】如何判定一个对象已死以及“标记-清除”、“标记-复制”、“标记-整理”三种垃圾收集算法

文章目录 0、如何判定一个对象的生死&#xff1f;1、上文提到的引用又是什么1、强引用&#xff1a;2、软引用&#xff1a;3、弱引用&#xff1a;4、虚引用&#xff1a; 2、垃圾收集算法1、标记-清除2、标记-复制优化&#xff1a;&#x1f447; 3、标记-整理 0、如何判定一个对象…

item_password-获得淘口令真实url

一、接口参数说明&#xff1a; item_password-获得淘口令真实url &#xff0c;点击更多API调试&#xff0c;请移步注册API账号点击获取测试key和secret 公共参数 请求地址: https://api-gw.onebound.cn/taobao/item_password 名称类型必须描述keyString是调用key&#xff08…

用cpolar生成的公网地址,对位于本地的Cloudreve网盘进行访问

文章目录 1、前言2、本地网站搭建2.1 环境使用2.2 支持组件选择2.3 网页安装2.4 测试和使用2.5 问题解决 3、本地网页发布3.1 cpolar云端设置3.2 cpolar本地设置 4、公网访问测试5、结语 1、前言 自云存储概念兴起已经有段时间了&#xff0c;各互联网大厂也纷纷加入战局&#…

Springboot集成ip2region离线IP地名映射-修订版

title: Springboot集成ip2region离线IP地名映射 date: 2020-12-16 11:15:34 categories: springboot description: Springboot集成ip2region离线IP地名映射 1. 背景2. 集成 2.1. 步骤2.2. 样例2.3. 响应实例DataBlock2.4. 响应实例RegionAddress 3. 打开浏览器4. 源码地址&…

米尔瑞萨RZ/G2L开发板-02 ffmpeg的使用和RTMP直播

最近不知道是不是熬夜太多&#xff0c;然后记忆力减退了&#xff1f; 因为板子回来以后我就迫不及待的试了一下板子&#xff0c;然后发现板子有SSH&#xff0c;但是并没有ffmpeg&#xff0c;最近总是在玩&#xff0c;然后今天说是把板子还原一下哇&#xff0c;然后把官方的固件…

Beats:安装及配置 Metricbeat (一)- 8.x

在我之前的文章&#xff1a; Beats&#xff1a;Beats 入门教程 &#xff08;一&#xff09;Beats&#xff1a;Beats 入门教程 &#xff08;二&#xff09; 我详细描述了如何在 Elastic Stack 7.x 安装及配置 Beats。在那里的安装&#xff0c;它通常不带有安全及 Elasticsearc…

Redis - 数据类型映射底层结构

简介 从数据类型上体现就是&#xff0c;同一个数据类型&#xff0c;在不同的情况下会使用不同的编码类型&#xff0c;底层所使用的的数据结构也不相同。 字符串对象 字符串对象的编码可以是 int、raw 和 embstr 三者之一。 embstr 编码是专门用于保存简短字符串的一种优化编…

Docker查看、创建、进入容器相关的命令

1.查看、创建、进入容器的指令 用-it指令创建出来的容器&#xff0c;创建完成之后会立马进入容器。退出之后立马关闭容器。 docker run -it --namec1 centos:7 /bin/bash退出容器&#xff1a; exit查看现在正在运行的容器命令&#xff1a; docker ps查看历史容器&#xff0…

解决Java中的“Unchecked cast: java.lang.Object to java.util.List”问题

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…

嵌入式系统中如何选择RTC电池?

RTC&#xff08;Real Time Clock&#xff09;是一种用于提供系统时间的独立定时器&#xff0c;它可以在系统断电或低功耗模式下继续运行&#xff0c;只需要一个后备电池作为供电源。在嵌入式系统中&#xff0c;选择合适的RTC电池时非常关键的&#xff0c;它会影响系统时间的准确…

CSS自己实现一个步骤条

前言 步骤条是一种用于引导用户按照特定流程完成任务的导航条&#xff0c;在各种分步表单交互场景中广泛应用。例如&#xff1a;在HIS系统-门诊医生站中的接诊场景中&#xff0c;我们就可以使用步骤条来实现。她的执行步骤分别是&#xff1a;门诊病历>遗嘱录入>完成接诊…