【题解-Acwing】1020. 潜水员
题目1020. 潜水员题目描述潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸一个为氧气一个为氮气。让潜水员下潜的深度需要各种数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少例如潜水员有5个气缸。每行三个数字为氧氮的升量和气缸的重量3 36 120 10 25 129 5 50 250 1 45 130 4 20 119如果潜水员需要5升的氧和60升的氮则总重最小为24912或者45号气缸。你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。输入格式第一行有2个整数 mn。它们表示氧氮各自需要的量。第二行为整数 k 表示气缸的个数。此后的 k 行每行包括aibici3个整数。这些各自是第 i 个气缸里的氧和氮的容量及气缸重量。输出格式仅一行包含一个整数为潜水员完成工作所需的气缸的重量总和的最低值。数据范围1 ≤ m ≤ 21,1 ≤ n ≤ 79,1 ≤ k ≤ 1000,1 ≤ ai≤ 21,1 ≤ bi≤ 79,1 ≤ ci≤ 800时空限制1s / 64MB输入样例5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119输出样例249思路特殊点j − v 1 [ i ] j-v1[i]j−v1[i]、k − v 2 [ i ] k-v2[i]k−v2[i]为负数怎么转移看成 0 就行。举个例子j − v 1 [ i ] j-v1[i]j−v1[i]为负数意思是不需要氧气了可以看成氧气为 0。初始化这里是取最小值因此将不可达的状态初始化为正无穷即可。对于所有的f [ 0 ] [ j ] [ k ] f[0][j][k]f[0][j][k]表示的是从前 0 个物品中选且氧≥ j ≥j≥j氮≥ k ≥k≥k的最小重量这些状态是不可达的初始化为正无穷。代码1三维数组#includebits/stdc.husingnamespacestd;constintN100010,M2110,K7910,INF0x3f3f3f3f;intn,V1,V2,v1[N],v2[N],w[N],f[N][M][K];intmain(){cinV1V2n;for(inti1;in;i)cinv1[i]v2[i]w[i];memset(f,0x3f,sizeoff);for(inti0;in;i)f[i][0][0]0;for(inti1;in;i)for(intj0;jV1;j)for(intk0;kV2;k)f[i][j][k]min(f[i-1][j][k],f[i-1][max(0,j-v1[i])][max(0,k-v2[i])]w[i]);coutf[n][V1][V2];return0;}代码2二维数组#includeiostream#includecstringusingnamespacestd;constintMaxV2110,MaxM7910;intN,V,M,f[MaxV][MaxM];intmain(){cinVMN;memset(f,0x3f,sizeoff);f[0][0]0;for(inti1;iN;i){intv,m,w;cinvmw;for(intjV;j0;j--){for(intkM;k0;k--){f[j][k]min(f[j][k],f[max(0,j-v)][max(0,k-m)]w);}}}coutf[V][M];return0;}结果

相关新闻

FanControl 完整指南:免费 Windows 风扇控制软件如何把噪音调没

FanControl 完整指南:免费 Windows 风扇控制软件如何把噪音调没

FanControl 完整指南:免费 Windows 风扇控制软件如何把噪音调没 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcode.com/GitHub_Tr…

2026/11/17 1:00:52 阅读更多 →
btop:5分钟上手这套终端系统资源监控工具

btop:5分钟上手这套终端系统资源监控工具

btop:5分钟上手这套终端系统资源监控工具 【免费下载链接】btop A monitor of resources 项目地址: https://gitcode.com/GitHub_Trending/bt/btop btop 是一个跑在终端里的 C 系统资源监控工具,CPU、内存、磁盘、网络、GPU 的实时数据全部画成图…

2026/10/4 14:58:37 阅读更多 →
移除任意子数组使剩余数组严格递增:LeetCode 2972「删除不可增子数组 II」双指针 O(n) 题解(codeforces-go 仓库精读)

移除任意子数组使剩余数组严格递增:LeetCode 2972「删除不可增子数组 II」双指针 O(n) 题解(codeforces-go 仓库精读)

科学计算 【免费下载链接】codeforces-go 算法竞赛模板库 by 灵茶山艾府 💭💡🎈 项目地址: https://gitcode.com/GitHub_Trending/co/codeforces-go 点击查看 免费下载 本文以 codeforces-go 仓库中 leetcode/biweekly/120/c/REA…

2026/10/6 7:21:47 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻