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

[POI 2004] MOS

一道很有意思的贪心题,似乎noi导刊上有?记不太清了,反正是做出来了。

题意

有一个桥,一个火把,一堆人。

这对人要过桥,过桥有一些条件。

  • 需要过桥的人有火把

  • 不可同时过两个以上

每次过桥的花费时间是两人中花费最高的那位。

询问最小的过桥花费。

注意,火把是必须有人带回的,这个火把不能凭空传送。

解法

这个其实并不难,我们发现 \(n\) 为 1, 2, 3 时的都很简单,我们从简单处入手。

对于 \(n=1\)

对于 \(n=2\)

对于 \(n=3\) 我们让最快的人分别带人过去再返回送火把,答案是所有人的花费之和。

但是对于 \(n>3\) 这个并不一定是正确的策略,我们但从这一次进行考虑这个确实是最优的,但是我们不能排除因为顺序而导致的不同。

比如有两个接近无限的数,这两个明显一起过更好,如果使用最快一个一个接明显不妥当。

所以我们多了一种策略,让最慢和次慢同行,显然最慢和次次慢更劣。

具体来讲第二种策略,我们让最快和次快先过,最快回来送火把,最慢和次慢过去,次快回来送火把。

这两种策略我们并不知道什么时候使用,所以直接 dp。

代码

#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
int n, a[MN], dp[MN];
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];dp[n]=a[n]+a[1];if(n==1){cout<<a[1]<<'\n';return 0;}for(int i=n-1; i; --i)dp[i]=min(a[i]+a[1]+dp[i+1],a[i+1]+a[2]+a[2]+a[1]+dp[i+2]);cout<<dp[3]+a[2]<<'\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=12347

相关文章:

  • 第03周 面向对象入门2与类的识别
  • 完整教程:启用GPU对模型进行推理,安装cuda toolkit cuDNN 9
  • 25秋周总结3
  • R ggplot2学习Nature子刊一张图,换数据即可用! - 指南
  • 2025-06-10.购买联想thinkpad 16p
  • 不会的好题总结
  • MySQL的Schema是什么? - 公众号
  • 与7无关的数
  • 推动安全研究多元化的10万美元捐赠计划
  • 20250919
  • 详细介绍:体验感满满—万物皆可插入
  • 支付宝的对账单下载
  • 1.6μVRMS超低噪声、20V、200mA低静态电流线性稳压器IBSP3030,替代LT3042、GM1201
  • [NOIP2022] 建造军营 解题报告
  • ABC 424 D-F 题解
  • 爱锋拍照工具 - 技术支持
  • 123213123
  • 详细介绍:项目首次推送到GitHub、指令步骤(下)
  • 计算多项式的值
  • 梦游天姥吟留别
  • Ubuntu操作便捷的系统下运用mysql、mongodb、redis
  • 03_Angular的突破性优势
  • 02_Angular现代前端框架的选型逻辑
  • 01_Angular时代的前端开发变革
  • 一堆杂题混刷
  • QQ 陌生人点赞 功能存在隐私泄露风险
  • Python爬虫实战——使用NetNut网页解锁器获取亚马逊电商资料
  • 2025 CCPC 网络赛
  • 安装windows11跳过账户登录
  • TCM安全学院夏季大促与免费网络安全课程发布