P1433 吃奶酪
#include <iostream>
#include <cmath>
using namespace std;
#define M 15
#define S(n) ((n) * (n))
double indx[M + 5], indy[M + 5], ans = 0, sum = 0;//坐标数组,从下标为1开始记录
int n, vis[M + 5] = { 0 };//vis数组,选过的数字标记为1,没选过的数字标记为0
double dis(int i, int j) {return sqrt(S(indx[i] - indx[j]) + S(indy[i] - indy[j]));
}
//c表示当前已经选了c个数字
//k表示最后一次选的是第k个点
void fun(int c, int k) {if (c == n) {if (!ans || ans > sum) ans = sum;return;}for (int i = 1; i <= n; i++) {if (vis[i]) continue;vis[i] = 1;sum += dis(i, k);fun(c + 1, i);vis[i] = 0;sum -= dis(i, k);}return;
}
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> indx[i] >> indy[i];}fun(0, 0);printf("%.2lf", ans);return 0;
}
8组超时,优化

#include <iostream>
#include <cmath>
using namespace std;
#define M 15
#define S(n) ((n) * (n))
double indx[M + 5], indy[M + 5], dp[70000][M + 5] = { 0 }, ans = 0; //坐标数组,从下标为1开始记录
//dp[i][j]:选择内容为i,最后一次选择的数字为j,的路径总长度
int n, vis[M + 5] = { 0 }; //vis数组,选过的数字标记为1,没选过的数字标记为0
double dis(int i, int j) { //返回第i个点到第j个点的距离return sqrt(S(indx[i] - indx[j]) + S(indy[i] - indy[j]));
}
//c表示当前已经选了c个数字
//k表示最后一次选的是第k个点
//m的二进制代表选择的内容
//sum表示这c个数字当前方案的路径总长度
void fun(int c, int k, int m, double sum) {if (c == n) {ans = sum;return;}dp[m][k] = sum; //到达一个新的节点,第一步就更新以m为内容,k为末端的路径长度for (int i = 1; i <= n; i++) {if (vis[i]) continue;int a = m + pow(2, i); //m如果自增,递归回来又要减,太麻烦,定义一个adouble d = dis(i, k); //后面最多用到三次,算出来方便用//以a为内容、i为路径已经被遍历过了,且之前的值小于等于这次遍历过去的值,那就不遍历过去了if (dp[a][i] != 0 && dp[a][i] <= sum + d) continue;//ans不为0且这次遍历过去sum超过ans,那就没必要过去了if (ans && ans <= sum + d) continue;vis[i] = 1;fun(c + 1, i, a, sum + d);vis[i] = 0;}return;
}
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> indx[i] >> indy[i];}fun(0, 0, 0, 0);printf("%.2lf", ans);return 0;
}

相关文章:
P1433 吃奶酪
#include <iostream> #include <cmath> using namespace std; #define M 15 #define S(n) ((n) * (n)) double indx[M 5], indy[M 5], ans 0, sum 0;//坐标数组,从下标为1开始记录 int n, vis[M 5] { 0 };//vis数组,选过的数字标记为1…...
c++string类的赋值问题
来看问题: 为什么呢?是因为定义string a""时候a没有占用空间,所以没有a[0],a[1],a[3]。如果说string a"hhhhhh",那么图中a[0],a[1],a[3]就有效了。正确的做法是用连接,或者是定义时写成string a(6…...
服务器中了mkp勒索病毒怎么办?mkp勒索病毒特点,解密数据恢复
Mkp勒索病毒是最近比较流行的勒索病毒,从10月份国庆节假期结束以来,云天数据恢复中心陆续收到很多企业的求助,企业的服务器被mkp勒索病毒攻击,导致企业的众多软件无法正常使用,像用友与金蝶软件都有遭受过mkp勒索病毒的…...
深入探析网络代理与网络安全
随着互联网的快速发展,网络安全问题日益突出,而网络代理技术正成为应对安全挑战的重要工具。本文将深入探讨Socks5代理、IP代理以及它们在网络安全、爬虫开发和HTTP协议中的关键作用,以期帮助读者更好地理解和应用这些技术。 1. Socks5代理&…...
如何开始使用 Kubernetes RBAC
基于角色的访问控制 (RBAC) 是一种用于定义用户帐户可以在 Kubernetes 集群中执行的操作的机制。启用 RBAC 可以降低与凭证盗窃和帐户接管相关的风险。向每个用户授予他们所需的最低权限集可以防止帐户拥有过多的特权。 大多数流行的 Kubernetes 发行版都从单个用户帐户开始,…...
8.简易无线通信
预备知识 Zigbee无线通信,需要高频的载波来提供发射效率,Zigbee模块之间要可以正常的收发,接收模块必须把接收频率设置和发射模块的载波频率一致。Zigbee有27个载波可以进行通信,载波叫做信道(无线通信的通道…...
渗透测试漏洞挖掘技巧
文章目录 一、使用.json进行敏感数据泄漏二、如何查找身份验证绕过漏洞三、在Drupal上找到隐藏的页面四、遗忘的数据库备份五、电子邮件地址payloads六、HTTP主机头:localhost七、通过篡改URI访问管理面板八、通过URL编码空格访问管理面板九、篡改URI绕过403十、Byp…...
Nginx - 反向代理与负载均衡
目录 一、Nginx 1.1、Nginx 下载 1.2、nginx 基础配置的认识 a)第一部分:全局块 b)第二部分:events 块 c)第三部分:http 块 http 块中 内嵌的 server 块 1.3、一些常用配置 1.3.1、location 匹配级…...
Linux网络编程系列之UDP组播
一、什么是UDP组播 UDP组播是指使用用户数据报协议(UDP)实现的组播方式。组播是一种数据传输方式,允许单一数据包同时传输到多个接收者。在UDP组播中,一个数据包可以被多个接收者同时接收,这样可以降低网络传输的负载和…...
设计模式~状态模式(state)-23
目录 (1)优点: (2)缺点: (3)使用场景: (4)注意事项: (5)应用实例: 代码 在状态模式(State Pattern)中,类的行为是基于它的状态改变的。这种类型的设计模式属于行为型模式。在状…...
linux环境下使用lighthouse与selenium
一、安装谷歌浏览器、谷歌浏览器驱动、lighthouse shell脚本 apt update && apt -y upgrade apt install -y curl curl -fsSL https://deb.nodesource.com/setup_18.x | bash apt install -y nodejs apt install -y npm npm install -g lighthouse apt-get install -y …...
NeuroImage | 右侧颞上回在语义规则学习中的作用:来自强化学习模型的证据
在现实生活中,许多规则的获取通常需要使用语言作为桥梁,特别是语义在信息传递中起着至关重要的作用。另外,个体使用的语言往往具有明显的奖励和惩罚元素,如赞扬和批评。一种常见的规则是寻求更多的赞扬,同时避免批评。…...
uni-app编程checkbox-group获取选中的每个checkbox的value值
uni-app编程checkbox-group获取选中的每个checkbox的value值_uniappcheckboxvalue-CSDN博客...
数组——螺旋矩阵II
文章目录 一、题目二、题解 题目顺序:代码随想录算法公开课,b站上有相应视频讲解 一、题目 59. Spiral Matrix II Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order. Example 1: Input: n …...
反范式化设计
反范式化设计与范式化设计相对立。范式化设计是将数据组织成多个表,以最小化数据的冗余和提高数据一致性。相反,反范式化设计是故意增加冗余,以提高查询性能和降低复杂性。反范式化设计通常用于需要高度优化的读取密集型应用程序,…...
CCF CSP认证 历年题目自练Day31
题目一 试题编号: 202206-1 试题名称: 归一化处理 时间限制: 500ms 内存限制: 512.0MB 题目背景 在机器学习中,对数据进行归一化处理是一种常用的技术。 将数据从各种各样分布调整为平均值为 0、方差为 1的标准分布&a…...
PCL点云处理之从两片点云中获取具有匹配关系的同名点对 (二百一十八)
PCL点云处理之从两片点云中获取具有匹配关系的同名点对 (二百一十八) 一、算法介绍二、算法实现1.代码2.效果一、算法介绍 点云配准的前提是,我们知道或者预测了一些匹配对,我们认为这些匹配对就是两片点云中的同名点,同名点就是由于激光扫描存在误差的关系,导致同一地物…...
MySQL Row size too large (> 8126)
错误信息 ERROR 1118 (42000) at line 901: Row size too large (> 8126). Changing some columns to TEXT or BLOB or using ROW_FORMATDYNAMIC or ROW_FORMATCOMPRESSED may help. In current row format, BLOB prefix of 768 bytes is stored inline. 错误原因 这个问题…...
HUAWEI(26)——防火墙双机热备
一、拓扑 二、需求 PC2 ping PC1 FW1与FW2双机热备,FW1为active,FW2为Standby,抢占延时1s VRRP 三、配置 1.IP地址,防火墙接口加入区域 防火墙用户名:admin 防火墙旧密码:Admin@123 防火墙新密码:admin@123 [FW1]interface GigabitEthernet 1/0/0 [FW1-GigabitEthe…...
【ArcGIS】NDVI估算植被覆盖度FVC
NDVI估算植被覆盖度FVC NDVI计算植被覆盖度FVC计算NDVI估算植被覆盖度FVC操作步骤Step1:调出栅格计算器工具Step2:查找NDVIStep3: 参考 NDVI计算 植被覆盖度FVC计算 NDVI估算植被覆盖度FVC操作步骤 Step1:调出栅格计算器工具 1、首先打开软件&#x…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
