2024HBCPC:E Breakfast II

news/2024/7/14 19:35:54/文章来源:https://blog.csdn.net/hjh2020012124/article/details/139275223
题目描述

作为一个合格的大学生,你不仅需要学习成绩好,还需要会买包子和鸡蛋。 今天,又轮到你们给你的导师买早饭了! 这一次你们一共需要给导师买 n n n 个包子和 m m m 个鸡蛋(请注意,这一次可能不再只买 32 32 32 个包子和 20 20 20 个鸡蛋)。 你的大学可以看作一个二维平面上 1 0 4 × 1 0 4 10^4×10^4 104×104 的正方形,横纵坐标的范围均为 0 ∼ 1 0 4 0∼10^4 0104。学校内一共有 3 3 3 间食堂,分别叫做综合食堂风味餐厅学生食堂。为了防止一个人买太多的早饭,每个人在每间食堂买的包子数和鸡蛋数分别不能超过 b b b e e e。 你们一共有 k k k 个人,第 i i i 个人所在宿舍的坐标为 ( X i , Y i ) (X_i,Y_i) (Xi,Yi)。你们需要选出若干同学,这些同学从各自的宿舍出发,前往食堂购买早饭后,然后将至少 n n n 个包子和 m m m 个鸡蛋送到导师的办公室。请注意,对于每位同学,每个食堂最多只能去购买一次。 你们需要进行商量,并决定哪些同学去买早饭、每个同学去哪些食堂、以及这些同学的路线,使得所有同学路线长度之和最小。如果某位同学无需购买早饭,那么他将待在宿舍里而不用前往办公室。

Input

第一行 3 3 3 个由空格分隔的整数 n , m , k ( 1 ≤ n , m , k ≤ 1 0 3 ) n,m,k (1≤n,m,k≤10^3) n,m,k(1n,m,k103),分别表示需要的包子数、鸡蛋数和学生个数。 第二行 2 2 2 个由空格分隔的整数 b , e ( 1 ≤ b ≤ n , 1 ≤ e ≤ m ) b,e (1≤b≤n,1≤e≤m) b,e(1bn,1em),分别表示每个人在每间食堂可以购买的包子与鸡蛋的上限。 第 3 ∼ 6 3∼6 36 行,每行两个由空格分隔的非负整数 x , y ( 0 ≤ x , y ≤ 104 ) x,y (0≤x,y≤104) x,y(0x,y104),依次表示综合食堂风味餐厅学生食堂办公室的坐标。 接下来 k k k 行,每行两个由空格分隔的非负整数 X i , Y i ( 0 ≤ X i , Y i ≤ 1 0 4 ) X_i,Y_i (0≤X_i,Y_i≤10^4) Xi,Yi(0Xi,Yi104),表示每位同学宿舍的坐标。 保证所有坐标互不相同,输入保证一定存在至少一种合法的买早饭方案

Output

一行一个浮点数,表示最小的路线长度之和。你的答案将被认为是正确的当且仅当与标准答案的相对或绝对误差不超过 1 0 − 6 10^{−6} 106

输入样例1
32 20 2
14 15
2 2
4 8
8 4
6 2
2 8
7 7
输出样例1
16.4759861592
输入样例2
32 20 2
32 20
2 2
4 8
8 4
6 2
2 8
7 7
输出样例2
5.9907047849
提示

对于样例一,最短的路线如图所示(其中 A , B , C A,B,C A,B,C 表示三个食堂, D D D 表示办公室, S 1 , S 2 S1,S2 S1,S2 表示学生的位置):
note.png

解题思路

分析题目可以得知,可以通过所需购买的包子和鸡蛋的个数推算出至少需要去食堂 m x = m a x ( ⌈ n b ⌉ , ⌈ m e ⌉ ) mx=max(\lceil \frac{n}{b} \rceil, \lceil \frac{m}{e} \rceil) mx=max(⌈bn,em⌉)次,每个学生之间也相互独立,所以考虑动态规划 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 考虑前 i i i 个学生,去了 j j j 次食堂所需的最短距离,问题就转换成了一个很经典的背包模型了。
在这里插入图片描述
其中, s [ i ] s[i] s[i] 维护的是第 i i i 个学生的信息,比如 s [ i ] . a s[i].a s[i].a 是经过综合食堂去办公室的最短距离, s [ i ] . a b s[i].ab s[i].ab 则是经过综合食堂,风味餐厅这两个食堂再去办公室的最短距离。

实现代码
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define debug(x) cerr << #x" = " << x << '\n';
using namespace std;void solve()
{int n, m, k, b, e;cin >> n >> m >> k >> b >> e;vector<pair<int, int>> D(4);for (int i = 0; i < 4; i++) cin >> D[i].x >> D[i].y;struct node{int x, y;double a, b, c, ab, ac, bc, abc;};vector<node> s(k + 10);auto get= [](int x1, int y1, int x2, int y2){double dx = x1 - x2;double dy = y1 - y2;return sqrt(dx * dx + dy * dy);};double at = get(D[0].x, D[0].y, D[3].x, D[3].y);double bt = get(D[1].x, D[1].y, D[3].x, D[3].y);double ct = get(D[2].x, D[2].y, D[3].x, D[3].y);double ab = get(D[0].x, D[0].y, D[1].x, D[1].y);double ac = get(D[0].x, D[0].y, D[2].x, D[2].y);double bc = get(D[1].x, D[1].y, D[2].x, D[2].y);for (int i = 1; i <= k; i++){cin >> s[i].x >> s[i].y;double a = get(s[i].x, s[i].y, D[0].x, D[0].y);double b = get(s[i].x, s[i].y, D[1].x, D[1].y);double c = get(s[i].x, s[i].y, D[2].x, D[2].y);s[i].a = a + at;s[i].b = b + bt;s[i].c = c + ct;s[i].ab = a + ab + bt;s[i].ab = min(s[i].ab, b + ab + at);s[i].ac = a + ac + ct;s[i].ac = min(s[i].ac, c + ac + at);s[i].bc = b + bc + ct;s[i].bc = min(s[i].bc, c + bc + bt);s[i].abc = a + ab + bc + ct;s[i].abc = min(s[i].abc, a + ac + bc + bt);s[i].abc = min(s[i].abc, b + ab + ac + ct);s[i].abc = min(s[i].abc, b + bc + ac + at);s[i].abc = min(s[i].abc, c + ac + ab + bt);s[i].abc = min(s[i].abc, c + bc + ab + at);}int mx = (n + b - 1) / b;mx = max(mx, (m + e - 1) / e);vector<vector<double>> dp(k + 10, vector<double>(mx + 10, 1e18));for (int i = 0; i <= k; i++) dp[i][0] = 0;for (int i = 1; i <= k; i++){for (int j = 0; j <= mx; j++){dp[i][j] = dp[i - 1][j];if (j >= 1) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + min(s[i].a, min(s[i].b, s[i].c)));if (j >= 2) dp[i][j] = min(dp[i][j], dp[i - 1][j - 2] + min(s[i].ab, min(s[i].ac, s[i].bc)));if (j >= 3) dp[i][j] = min(dp[i][j], dp[i - 1][j - 3] + s[i].abc);}}cout << fixed << setprecision(10) << dp[k][mx] << '\n';
}signed main()
{// freopen("Sample.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;// cin >> T;while (T--) solve();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1054265.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

网关(GateWay)- 快速使用

引入依赖 <!-- gateway --> <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-gateway</artifactId> </dependency> 路由配置 server:port: 8088 spring:application:name: api-gatew…

Clickhouse Bitmap 类型操作总结—— Clickhouse 基础篇(四)

文章目录 创建 Bitmap 对象Bitmap 转换为整数数组计算总数&#xff08;去重&#xff09;值指定start, end 索引生成子 Bitmap指定 start 索引和数量限制生成子 Bitmap指定偏移量生成子 Bitmap是否包含指定元素两个 Bitmap 是否存在相同元素一个是否为另一个 Bitmap 的子集求最小…

25 使用MapReduce编程了解垃圾分类情况

测试数据中1表示可回收垃圾&#xff0c;2表示有害垃圾&#xff0c;4表示湿垃圾&#xff0c;8表示干垃圾。 统计数据中各类型垃圾的数量&#xff0c;分别存储可回收垃圾、有害垃圾、湿垃圾和干垃圾的统计结果。 &#xff08;存储到4个不同文件中&#xff0c;垃圾信息&#xff0…

VsCode创建Python虚拟环境

不同的项目&#xff0c;大多使用不同的版本与包&#xff0c;为每个项目创建不同的环境&#xff0c;可以防止版本等的不同而带来的影响。 Python自3.3版本之后&#xff0c;官方自带了用于创建虚拟环境的venv模块&#xff0c;以下将介绍venv模块在Python虚拟环境的用法。 1.安装相…

合约构成-成员变量、函数、事件event、修饰器modifier及构造函数

合约的基本结构 合约中的成员变量合约中的成员函数Event&#xff08;事件&#xff09;、modifier(修饰器)与constructor&#xff08;构造函数:实例产生的时候执行&#xff09; Event事件 modifier construcor 1、成员变量 概念&#xff1a;存储合约状态的变量 声明方法&a…

100个 Unity小游戏系列六 -Unity 抽奖游戏专题四 翻卡游戏

一、演示效果 二、知识点讲解 2.1 布局 void CreateItems(){reward_data_list reward_data_list ?? new List<RewardData>();reward_data_list.Clear();for (int i 0; i < ItemCount; i){GameObject item;if (i 1 < itemParent.childCount){item itemParent…

母婴商城购物网站,基于 SpringBoot+Vue+MySQL 开发的前后端分离的母婴商城购物网站设计实现

目录 一. 前言 二. 功能模块 2.1. 前台功能 2.2. 用户信息管理 2.3. 商品分类管理 2.4. 商品信息管理 2.5. 商品资讯管理 三. 部分代码实现 四. 源码下载 一. 前言 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&a…

多输入多输出 | MATLAB实现BiTCN(双向时间卷积神经网络)多输入多输出预测

多输入多输出 | MATLAB实现BiTCN(双向时间卷积神经网络)多输入多输出预测 目录 多输入多输出 | MATLAB实现BiTCN(双向时间卷积神经网络)多输入多输出预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab实现BiTCN双向时间卷积神经网络多输入多输出预测 1.data为数据…

Mac连接虚拟机(Linux系统)

1.确定虚拟机的IP地址 ifconfig //终端命令&#xff0c;查询ip地址 sudo apt install net-tools 安装完成后再次执行 ifconfig&#xff1a; 2.安装SSH&#xff08;加密远程登录协议&#xff09; (1).安装OpenSSH服务器软件包&#xff1a; sudo apt-get install openssh-ser…

【最优化方法】实验一 熟悉MATLAB基本功能

实验一  熟悉MATLAB基本功能 实验的目的和要求&#xff1a;在本次实验中&#xff0c;通过亲临使用MATLAB&#xff0c;对该软件做一全面了解并掌握重点内容。 实验内容&#xff1a; &#xff11;、全面了解MATLAB系统 &#xff12;、实验常用工具的具体操作和功能 学习建…

机器学习大模型驱动:未来的趋势与应用

文章目录 &#x1f4d1;前言一、什么是机器学习大模型&#xff1f;1.1 大模型的特点1.2 大模型的技术基础 二、大模型的技术实现2.1 Transformer 架构2.2 预训练和微调2.3 模型并行和数据并行 三、大模型的应用场景3.1 自然语言处理&#xff08;NLP&#xff09;3.2 计算机视觉&…

vue学习汇总

目录 一、vue基本语法 1.插值表达式 {{}} 2.显示数据(v-text)和(v-html) 3.事件处理(v-on) 4.循环遍历(v-for) 5.判断语法(v-if) 6.元素显示与隐藏(v-show) 7.动态设置属性(v-bind) 8.数据双向绑定(v-model) 9.计算属性 二、vue组件 1.使用组件的三个步骤 2.注册组…

采用Java+ SpringBoot+ IntelliJ+idea开发的ADR药物不良反应监测系统源码

采用Java SpringBoot IntelliJidea开发的ADR药物不良反应监测系统源码 ADR药物不良反应监测系统有哪些应用场景&#xff1f; ADR药物不良反应监测系统有哪些应用场景&#xff1f; ADR药物不良反应监测系统具有广泛的应用场景&#xff0c;以下是一些主要的应用场景&#xff1a…

建立FTP服务器

文章目录 建立FTP服务器1. 使用VMware安装CentOS 7虚拟机。2. 安装完虚拟机后&#xff0c;进入虚拟机&#xff0c;修改网络配置&#xff08;onboot改为yes&#xff09;并重启网络服务&#xff0c;查看相应IP地址&#xff0c;并使用远程连接软件进行连接。3.配置yum源&#xff0…

深入了解Nginx(一):Nginx核心原理

一、Nginx核心原理 本节为大家介绍Nginx的核心原理,包含Reactor模型、Nginx的模块化设计、Nginx的请求处理阶段. &#xff08;本文源自微博客,且已获得授权&#xff09; 1.1、Reactor模型 Nginx对高并发IO的处理使用了Reactor事件驱动模型。Reactor模型的基本组件包含时间收集…

Python爬虫实战(实战篇)—17获取【CSDN某一专栏】数据转为Markdown列表放入文章中

文章目录 专栏导读背景结果预览1、页面分析2、通过返回数据发现适合利用lxmlxpath3、进行Markdown语言拼接总结 专栏导读 在这里插入图片描述 &#x1f525;&#x1f525;本文已收录于《Python基础篇爬虫》 &#x1f251;&#x1f251;本专栏专门针对于有爬虫基础准备的一套基…

gitlab将本地文件项目上传至gitlab服务

打开gitlab网页界面&#xff0c;登陆管理员账号 &#xff08;测试服务器安装的gitlab&#xff0c;浏览器输入ip或配置的gitlab地址&#xff09; 创建新项目 使用gitlab创建项目 创建一个新项目&#xff08;忽略分组&#xff09; &#xff08;忽略分组&#xff09; 在创建工…

【CTF Web】CTFShow web5 Writeup(SQL注入+PHP+位运算)

web5 1 阿呆被老板狂骂一通&#xff0c;决定改掉自己大意的毛病&#xff0c;痛下杀手&#xff0c;修补漏洞。 解法 注意到&#xff1a; <!-- flag in id 1000 -->拦截很多种字符&#xff0c;连 select 也不给用了。 if(preg_match("/\|\"|or|\||\-|\\\|\/|\…

深入分析 Android Activity (一)

文章目录 深入分析 Android Activity (一)1. Activity 的窗口管理2. Activity 的生命周期管理onCreateonStartonResumeonPauseonStoponDestroyonRestart 3. Activity 与 Fragment 的交互添加 FragmentFragment 的生命周期 4. Activity 的任务和返回栈5. 配置变化处理 总结 深入…

【实用的 IDEA 配置和操作技巧总结】

前置知识 IDEA的设置快捷键为ctrlalts键&#xff0c;后文介绍IDEA常见的配置就不再赘述这一点了。 基础配置 取消默认打开上次项目 日常开发都会打开不同的项目&#xff0c;初次安装IDEA之后&#xff0c;每次打开IDEA都会开启上一次启动的项目&#xff0c;所以我们需要进入设…