当前位置: 首页 > 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…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...