题目:售货员的难题(状压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;
}
相关文章:
题目:售货员的难题(状压dp)
售货员的难题 题目描述输入输出格式输入格式:输出格式: 输入输出样例输入样例#1:输出样例#1: 思路AC代码: 题目描述 某乡有n个村庄( 1 < n < 16 ),有一个售货员,他要到各个村庄去售货&am…...
Linux 的 MySQL 5.x - 关于 Windows 10 的 Navicat Premium 导入 Excel (.xlsx)文件,报错问题集锦
问题 [ERR] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:01’ for column ‘xxx_time’ 解决方法: Windows 则是 my.ini Linux 系统则是 /etc/my.cnf 修改my.ini配置文件,建议修改前新备份下, my.ini中查找sql-mode࿰…...
基于IP网络的存储协议——iSCSI
文章首发地址 iSCSI(Internet Small Computer System Interface)是一种基于IP网络的存储协议,它能够在TCP/IP网络上实现SCSI协议,使得不同的主机可以通过网络共享存储设备。iSCSI可以将存储设备映射到本地主机上,使得主…...
神经网络基础-神经网络补充概念-27-深层网络中的前向传播
概念 深层神经网络中的前向传播是指从输入数据开始,逐层计算每个神经元的输出值,直到得到最终的预测值。 一般步骤 1输入数据传递: 将输入数据传递给网络的输入层。输入数据通常是一个特征矩阵,每一列代表一个样本,…...
用cpolar生成的公网地址,对位于本地的Cloudreve网盘进行访问
文章目录 1、前言2、本地网站搭建2.1 环境使用2.2 支持组件选择2.3 网页安装2.4 测试和使用2.5 问题解决 3、本地网页发布3.1 cpolar云端设置3.2 cpolar本地设置 4、公网访问测试5、结语 1、前言 自云存储概念兴起已经有段时间了,各互联网大厂也纷纷加入战局&#…...
docker compose部署zookeeper
单机部署 新建docker-compose.yaml version: 3 services:zookeeper:image: zookeeper:3.5.7container_name: base-zookeeperhostname: zookeeperprivileged: truerestart: alwaysports:- 2181:2181environment:TZ: "Asia/Shanghai"volumes:- ./volumes/zookeeper/d…...
【SA8295P 源码分析】77 - QNX Camera 之 ais_server 服务 源码分析
【SA8295P 源码分析】77 - QNX Camera 之 ais_server 服务 源码分析 一、QNX 侧 AIS 摄像头服务启动命令1.1 ais_server:在 ifs_camera.img 中启动1.2 ais_be_server:在 startup.sh 中启动二、ais_server 源码分析2.1 ais_server 编译脚本分析2.2 ais_server.c:监听 ais_cli…...
内网搭建电影网站的实现和进行公网访问
如何实现内网搭建电影网站并进行公网访问 文章目录 如何实现内网搭建电影网站并进行公网访问前言1. 把软件分别安装到本地电脑上1.1 打开PHPStudy软件,安装一系列电影网站所需的支持软件1.2 设置MacCNS10的运行环境1.3 进入电影网页的安装程序1.4 对运行环境进行检测…...
5.4 常用滤波算法
文章目录 代码filter.cfilter.h 代码 filter.c #include <stdio.h> #include "stm32f429xx.h" #include <string.h> /* 限幅滤波A方法: 根据经验判断,确定两次采样允许的最大偏差值(设为A),每…...
【算法系列篇】双指针
文章目录 前言什么是双指针算法1.移动零1.1 题目要求1.2 做题思路1.3 Java代码实现 2.复写零2.1 题目要求2.2 做题思路2.3 Java代码实现 3.快乐数3.1 题目要求3.2 做题思路3.3 Java代码实现 4.盛最多水的容器4.1 题目要求4.2 做题思路4.3 Java代码实现 5.有效三角形的个数5.1 题…...
Web和云开发,Rust会起飞?
Web和云开发,Rust会起飞? 一、前言 二、大厂偏爱,Rust的未来 三、Rust做Web的雄心 四、有必要换Rust做Web? 1.效率和性能 2.可靠性和可维护性 五、Rust先苦后甜 六、用Rust前的几个问题 七、开发界的强者 一、前言 去年…...
深度学习项目学习
文章目录 torchvisiontorchvision.transforms.Compose()类 DataLoader类torch.nntorch.nn.Moudletorch.nn.Sequential模型容器nn.CrossEntropyLoss()交叉熵损失函数 numpynumpy.random. shuffle(x) torchvision torchvision和pytorch的关系: torchvision是PyTorch的…...
【3Ds Max】弯曲命令的简单使用
简介 在3ds Max中,"弯曲"(Bend)是一种用于在平面或曲面上创建弯曲效果的建模命令。使用弯曲命令,您可以将对象沿特定轴向弯曲,从而创建出各种弯曲的几何形状。以下是使用3ds Max中的弯曲命令的基本步骤&…...
opencv基础:几个常用窗口方法
开始说了一些opencv中的一些常用方法。 namedWindow方法 在OpenCV中,namedWindow函数用于创建一个窗口,并给它指定一个名字。这个函数的基本语法如下: import cv2cv2.namedWindow(窗口名称, 标识 )窗口名称:其实窗口名称&…...
web后端解决跨域问题
目录 什么是跨域问题 为什么限制访问 解决 什么是跨域问题 域是指从一个域名的网页去请求另一个域名的资源。比如从www.baidu.com 页面去请求 www.google.com 的资源。但是一般情况下不能这么做,它是由浏览器的同源策略造成的,是浏览器对js施加的安全…...
06 json数据解析和列表控件
内容回顾 json数据解析 json ----- 对要传输的数据进行封装的工具 json是由json数组([]) 和 json对象({})在qt中,对JSON数据进行处理(解析和打包) JSON数据处理所要包含的类: QJsonDocument -----它的作用是将数据转换成json文档 QJsonArray ---- json数组,就是封装多个…...
分布式 - 消息队列Kafka:Kafka生产者架构和配置参数
文章目录 1. kafka 生产者发送消息整体架构2. Kafka 生产者重要参数配置01. acks02. 消息传递时间03. linger.ms04. buffer.memory05. batch.size06. max.in.flight.requests.per.connection07. compression.type08. max.request.size09. receive.buffer.bytes和 send.buffer.b…...
MAUI+Blazor:windows 打包踩坑
文章目录 前言MSIX安装文件如何发布选择Windows平台旁加载自定义签名版本号安装 总结 前言 最近打算研究一下MAUIBlazor,争取在今年年底之前彻底搞懂MAUIBlazor的安装模式, MSIX安装文件 Windows 4种安装程序格式MSI,EXE、AppX和MSIX优缺点…...
web集群学习:搭建 LNMP应用环境
目录 LNMP的介绍: LNMP组合工作流程: FastCGI介绍: 1、什么是 CGI 2、什么是 FastCGI 配置LNMP 1、部署LNMP环境 2、配置LNMP环境 LNMP的介绍: 随着 Nginx Web 服务的逐渐流行,又岀现了新的 Web 服务环境组合—…...
我的创作纪念日(256天)
前言 结缘 我与csdn的结缘,之前在创作纪念日(128天)便已提到,今在此便不再多言 收获 很惭愧,自六月底至八月中旬,因为忙于找工作,奔赴面试求职之际,写博客没有像之前那么勤&#x…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
MySQL体系架构解析(三):MySQL目录与启动配置全解析
MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录,这个目录下存放着许多可执行文件。与其他系统的可执行文件类似,这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中,用…...
41道Django高频题整理(附答案背诵版)
解释一下 Django 和 Tornado 的关系? Django和Tornado都是Python的web框架,但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架,鼓励快速开发和干净、实用的设计。它遵循MVC设计,并强调代码复用。Django有…...
GeoServer发布PostgreSQL图层后WFS查询无主键字段
在使用 GeoServer(版本 2.22.2) 发布 PostgreSQL(PostGIS)中的表为地图服务时,常常会遇到一个小问题: WFS 查询中,主键字段(如 id)莫名其妙地消失了! 即使你在…...
简单介绍C++中 string与wstring
在C中,string和wstring是两种用于处理不同字符编码的字符串类型,分别基于char和wchar_t字符类型。以下是它们的详细说明和对比: 1. 基础定义 string 类型:std::string 字符类型:char(通常为8位)…...
C# WPF 左右布局实现学习笔记(1)
开发流程视频: https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码: GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用(.NET Framework) 2.…...
GB/T 43887-2024 核级柔性石墨板材检测
核级柔性石墨板材是指以可膨胀石墨为原料、未经改性和增强、用于核工业的核级柔性石墨板材。 GB/T 43887-2024核级柔性石墨板材检测检测指标: 测试项目 测试标准 外观 GB/T 43887 尺寸偏差 GB/T 43887 化学成分 GB/T 43887 密度偏差 GB/T 43887 拉伸强度…...
