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

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;//坐标数组&#xff0c;从下标为1开始记录 int n, vis[M 5] { 0 };//vis数组&#xff0c;选过的数字标记为1…...

c++string类的赋值问题

来看问题&#xff1a; 为什么呢&#xff1f;是因为定义string a""时候a没有占用空间&#xff0c;所以没有a[0],a[1],a[3]。如果说string a"hhhhhh"&#xff0c;那么图中a[0],a[1],a[3]就有效了。正确的做法是用连接&#xff0c;或者是定义时写成string a(6…...

服务器中了mkp勒索病毒怎么办?mkp勒索病毒特点,解密数据恢复

Mkp勒索病毒是最近比较流行的勒索病毒&#xff0c;从10月份国庆节假期结束以来&#xff0c;云天数据恢复中心陆续收到很多企业的求助&#xff0c;企业的服务器被mkp勒索病毒攻击&#xff0c;导致企业的众多软件无法正常使用&#xff0c;像用友与金蝶软件都有遭受过mkp勒索病毒的…...

深入探析网络代理与网络安全

随着互联网的快速发展&#xff0c;网络安全问题日益突出&#xff0c;而网络代理技术正成为应对安全挑战的重要工具。本文将深入探讨Socks5代理、IP代理以及它们在网络安全、爬虫开发和HTTP协议中的关键作用&#xff0c;以期帮助读者更好地理解和应用这些技术。 1. Socks5代理&…...

如何开始使用 Kubernetes RBAC

基于角色的访问控制 (RBAC) 是一种用于定义用户帐户可以在 Kubernetes 集群中执行的操作的机制。启用 RBAC 可以降低与凭证盗窃和帐户接管相关的风险。向每个用户授予他们所需的最低权限集可以防止帐户拥有过多的特权。 大多数流行的 Kubernetes 发行版都从单个用户帐户开始,…...

8.简易无线通信

预备知识 Zigbee无线通信&#xff0c;需要高频的载波来提供发射效率&#xff0c;Zigbee模块之间要可以正常的收发&#xff0c;接收模块必须把接收频率设置和发射模块的载波频率一致。Zigbee有27个载波可以进行通信&#xff0c;载波叫做信道&#xff08;无线通信的通道&#xf…...

渗透测试漏洞挖掘技巧

文章目录 一、使用.json进行敏感数据泄漏二、如何查找身份验证绕过漏洞三、在Drupal上找到隐藏的页面四、遗忘的数据库备份五、电子邮件地址payloads六、HTTP主机头&#xff1a;localhost七、通过篡改URI访问管理面板八、通过URL编码空格访问管理面板九、篡改URI绕过403十、Byp…...

Nginx - 反向代理与负载均衡

目录 一、Nginx 1.1、Nginx 下载 1.2、nginx 基础配置的认识 a&#xff09;第一部分&#xff1a;全局块 b&#xff09;第二部分&#xff1a;events 块 c&#xff09;第三部分&#xff1a;http 块 http 块中 内嵌的 server 块 1.3、一些常用配置 1.3.1、location 匹配级…...

Linux网络编程系列之UDP组播

一、什么是UDP组播 UDP组播是指使用用户数据报协议&#xff08;UDP&#xff09;实现的组播方式。组播是一种数据传输方式&#xff0c;允许单一数据包同时传输到多个接收者。在UDP组播中&#xff0c;一个数据包可以被多个接收者同时接收&#xff0c;这样可以降低网络传输的负载和…...

设计模式~状态模式(state)-23

目录 (1)优点&#xff1a; (2)缺点&#xff1a; (3)使用场景&#xff1a; (4)注意事项&#xff1a; (5)应用实例&#xff1a; 代码 在状态模式&#xff08;State Pattern&#xff09;中&#xff0c;类的行为是基于它的状态改变的。这种类型的设计模式属于行为型模式。在状…...

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 | 右侧颞上回在语义规则学习中的作用:来自强化学习模型的证据

在现实生活中&#xff0c;许多规则的获取通常需要使用语言作为桥梁&#xff0c;特别是语义在信息传递中起着至关重要的作用。另外&#xff0c;个体使用的语言往往具有明显的奖励和惩罚元素&#xff0c;如赞扬和批评。一种常见的规则是寻求更多的赞扬&#xff0c;同时避免批评。…...

uni-app编程checkbox-group获取选中的每个checkbox的value值

uni-app编程checkbox-group获取选中的每个checkbox的value值_uniappcheckboxvalue-CSDN博客...

数组——螺旋矩阵II

文章目录 一、题目二、题解 题目顺序&#xff1a;代码随想录算法公开课&#xff0c;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 …...

反范式化设计

反范式化设计与范式化设计相对立。范式化设计是将数据组织成多个表&#xff0c;以最小化数据的冗余和提高数据一致性。相反&#xff0c;反范式化设计是故意增加冗余&#xff0c;以提高查询性能和降低复杂性。反范式化设计通常用于需要高度优化的读取密集型应用程序&#xff0c;…...

CCF CSP认证 历年题目自练Day31

题目一 试题编号&#xff1a; 202206-1 试题名称&#xff1a; 归一化处理 时间限制&#xff1a; 500ms 内存限制&#xff1a; 512.0MB 题目背景 在机器学习中&#xff0c;对数据进行归一化处理是一种常用的技术。 将数据从各种各样分布调整为平均值为 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&#xff1a;调出栅格计算器工具Step2:查找NDVIStep3: 参考 NDVI计算 植被覆盖度FVC计算 NDVI估算植被覆盖度FVC操作步骤 Step1&#xff1a;调出栅格计算器工具 1、首先打开软件&#x…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...

运行vue项目报错 errors and 0 warnings potentially fixable with the `--fix` option.

报错 找到package.json文件 找到这个修改成 "lint": "eslint --fix --ext .js,.vue src" 为elsint有配置结尾换行符&#xff0c;最后运行&#xff1a;npm run lint --fix...

STL 2迭代器

文章目录 1.迭代器2.输入迭代器3.输出迭代器1.插入迭代器 4.前向迭代器5.双向迭代器6.随机访问迭代器7.不同容器返回的迭代器类型1.输入 / 输出迭代器2.前向迭代器3.双向迭代器4.随机访问迭代器5.特殊迭代器适配器6.为什么 unordered_set 只提供前向迭代器&#xff1f; 1.迭代器…...