当前位置: 首页 > news >正文

题目:售货员的难题(状压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)

售货员的难题 题目描述输入输出格式输入格式&#xff1a;输出格式&#xff1a; 输入输出样例输入样例#1&#xff1a;输出样例#1&#xff1a; 思路AC代码&#xff1a; 题目描述 某乡有n个村庄( 1 < n < 16 )&#xff0c;有一个售货员&#xff0c;他要到各个村庄去售货&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’ 解决方法&#xff1a; Windows 则是 my.ini Linux 系统则是 /etc/my.cnf 修改my.ini配置文件&#xff0c;建议修改前新备份下&#xff0c; my.ini中查找sql-mode&#xff0…...

基于IP网络的存储协议——iSCSI

文章首发地址 iSCSI&#xff08;Internet Small Computer System Interface&#xff09;是一种基于IP网络的存储协议&#xff0c;它能够在TCP/IP网络上实现SCSI协议&#xff0c;使得不同的主机可以通过网络共享存储设备。iSCSI可以将存储设备映射到本地主机上&#xff0c;使得主…...

神经网络基础-神经网络补充概念-27-深层网络中的前向传播

概念 深层神经网络中的前向传播是指从输入数据开始&#xff0c;逐层计算每个神经元的输出值&#xff0c;直到得到最终的预测值。 一般步骤 1输入数据传递&#xff1a; 将输入数据传递给网络的输入层。输入数据通常是一个特征矩阵&#xff0c;每一列代表一个样本&#xff0c;…...

用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;各互联网大厂也纷纷加入战局&#…...

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软件&#xff0c;安装一系列电影网站所需的支持软件1.2 设置MacCNS10的运行环境1.3 进入电影网页的安装程序1.4 对运行环境进行检测…...

5.4 常用滤波算法

文章目录 代码filter.cfilter.h 代码 filter.c #include <stdio.h> #include "stm32f429xx.h" #include <string.h> /* 限幅滤波A方法&#xff1a; 根据经验判断&#xff0c;确定两次采样允许的最大偏差值&#xff08;设为A&#xff09;&#xff0c;每…...

【算法系列篇】双指针

文章目录 前言什么是双指针算法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和云开发&#xff0c;Rust会起飞&#xff1f; 一、前言 二、大厂偏爱&#xff0c;Rust的未来 三、Rust做Web的雄心 四、有必要换Rust做Web&#xff1f; 1.效率和性能 2.可靠性和可维护性 五、Rust先苦后甜 六、用Rust前的几个问题 七、开发界的强者 一、前言 去年…...

深度学习项目学习

文章目录 torchvisiontorchvision.transforms.Compose()类 DataLoader类torch.nntorch.nn.Moudletorch.nn.Sequential模型容器nn.CrossEntropyLoss()交叉熵损失函数 numpynumpy.random. shuffle(x) torchvision torchvision和pytorch的关系&#xff1a; torchvision是PyTorch的…...

【3Ds Max】弯曲命令的简单使用

简介 在3ds Max中&#xff0c;"弯曲"&#xff08;Bend&#xff09;是一种用于在平面或曲面上创建弯曲效果的建模命令。使用弯曲命令&#xff0c;您可以将对象沿特定轴向弯曲&#xff0c;从而创建出各种弯曲的几何形状。以下是使用3ds Max中的弯曲命令的基本步骤&…...

opencv基础:几个常用窗口方法

开始说了一些opencv中的一些常用方法。 namedWindow方法 在OpenCV中&#xff0c;namedWindow函数用于创建一个窗口&#xff0c;并给它指定一个名字。这个函数的基本语法如下&#xff1a; import cv2cv2.namedWindow(窗口名称, 标识 )窗口名称&#xff1a;其实窗口名称&…...

web后端解决跨域问题

目录 什么是跨域问题 为什么限制访问 解决 什么是跨域问题 域是指从一个域名的网页去请求另一个域名的资源。比如从www.baidu.com 页面去请求 www.google.com 的资源。但是一般情况下不能这么做&#xff0c;它是由浏览器的同源策略造成的&#xff0c;是浏览器对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&#xff0c;争取在今年年底之前彻底搞懂MAUIBlazor的安装模式&#xff0c; MSIX安装文件 Windows 4种安装程序格式MSI&#xff0c;EXE、AppX和MSIX优缺点…...

web集群学习:搭建 LNMP应用环境

目录 LNMP的介绍&#xff1a; LNMP组合工作流程&#xff1a; FastCGI介绍&#xff1a; 1、什么是 CGI 2、什么是 FastCGI 配置LNMP 1、部署LNMP环境 2、配置LNMP环境 LNMP的介绍&#xff1a; 随着 Nginx Web 服务的逐渐流行&#xff0c;又岀现了新的 Web 服务环境组合—…...

我的创作纪念日(256天)

前言 结缘 我与csdn的结缘&#xff0c;之前在创作纪念日&#xff08;128天&#xff09;便已提到&#xff0c;今在此便不再多言 收获 很惭愧&#xff0c;自六月底至八月中旬&#xff0c;因为忙于找工作&#xff0c;奔赴面试求职之际&#xff0c;写博客没有像之前那么勤&#x…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...