594: Maximum Tape Utilization Ratio

news/2025/1/1 21:32:05/

解法:

对于该题有以下错误(敬希评论区指正

1.dp定义在全局会wa

struct node {int count;  // 当前容量下能够存储的程序数量int sum;    // 当前容量下所占用的磁带长度vector<int> path;  // 当前容量下选择的程序的路径(存放的程序长度)
}dp[N];

2.不取等于情况会wa

dp[j].sum < dp[j - a[i]].sum + a[i])

3.正序遍历程序会wa

for (int i = 0; i < n; i++)

代码:

#include<bits/stdc++.h>
using namespace std;const int N = 1e4;  // 定义一个常量 N,最大可能的磁带容量大小int a[N];  // 存储每个程序占用的磁带长度// 定义一个结构体 node,存储每个容量下的状态
struct node {int count;  // 当前容量下能够存储的程序数量int sum;    // 当前容量下所占用的磁带长度vector<int> path;  // 当前容量下选择的程序的路径(存放的程序长度)
};int main() {int n, m;cin >> n >> m;  // 输入程序的数量 n 和磁带的容量 mnode dp[N];  // dp 数组,用于存储每个磁带容量下的状态// 输入每个程序占用的磁带长度for (int i = 0; i < n; i++) {cin >> a[i];}// 遍历程序,采用逆序遍历程序for (int i = n - 1; i >= 0; i--) {  // 逆序遍历程序,确保每个程序只被选择一次// 遍历每个可能的磁带容量,从大到小for (int j = m; j >= a[i]; j--) {  // 逆序遍历容量,确保不会重复使用程序// 如果选择程序 i 后,存储的程序数更多,或者程序数相同但占用磁带长度更小if (dp[j].count < dp[j - a[i]].count + 1 || (dp[j].count == dp[j - a[i]].count + 1 && dp[j].sum <= dp[j - a[i]].sum + a[i])) {// 更新 dp[j]:增加程序数量、更新占用的磁带长度和路径dp[j].count = dp[j - a[i]].count + 1;  // 更新当前容量 j 下的程序数dp[j].sum = dp[j - a[i]].sum + a[i];  // 更新当前容量 j 下的磁带长度dp[j].path = dp[j - a[i]].path;  // 继承先前的路径dp[j].path.push_back(a[i]);  // 将当前程序加入路径}}}// 输出结果:最大存储程序数和最大利用率的磁带长度cout << dp[m].count << " " << dp[m].sum << endl;// 输出存放在磁带上的每个程序的长度for (int i = dp[m].path.size() - 1; i >= 0; i--) {cout << dp[m].path[i] << " ";  // 按照逆序输出选中的程序长度}
}

解法二:

case1:程序总消耗内存<=磁带长度,输出总程序数,程序总消耗内存

case2:程序总消耗内存>磁带长度,

        1.保证存储最多程序:从小到大依次加入sum直至sum+L[i]>磁带长度

        2.在两侧数组中各选一个交换,交换后得到的磁带长度-sum是最小的


http://www.ppmy.cn/news/1559411.html

相关文章

输煤皮带智能巡检解决方案

输煤皮带系统作为煤炭运输的重要环节&#xff0c;是火力发电厂和煤炭化工等行业的重要基础设施。系统通常运行在高温、高湿、粉尘严重的环境中&#xff0c;机械故障、皮带磨损和跑偏等问题时有发生&#xff0c;严重影响生产效率和安全。传统的人工巡检方式存在频率不足、覆盖面…

Python的简单爬虫框架

爬虫为网络爬虫&#xff08;又称为网页蜘蛛&#xff0c;网络机器人&#xff0c;在FOAF社区中间&#xff0c;更经常的称为网页追逐者&#xff09;&#xff0c;是一种按照一定的规则&#xff0c;自动地抓取万维网信息的程序或者脚本。另外一些不常使用的名字还有蚂蚁、自动索引、…

golang LeetCode 热题 100(动态规划)-更新中

爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a;输入&#xff1a;n 2 输出&#xff1a;2 解释&#xff1a;有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶 示例 2&…

Ubuntu 24.04.1 LTS 配置静态固定IP地址

查看网络配置信息 ip addr使用该命令查看网卡名字&#xff0c;一般是ens33或者ens32 修改配置文件 打开 /etc/netplan/下面的yaml配置文件 根据自己的需要配置 network:ethernets:ens33: # 配置的网卡的名称addresses: [192.168.23.140/24] # 配置的静态ip地址和掩码d…

【智能制造-50】雅可比矩阵在机器人中如何应用

在机器人领域&#xff0c;雅可比矩阵是一个非常重要的工具&#xff0c;有着广泛的应用&#xff1a; 运动学分析 在机器人的运动学和动力学分析中&#xff0c;雅可比矩阵用于描述机器人末端执行器的位姿与关节变量之间的关系&#xff0c;以及力与力矩在不同坐标系之间的转换。…

Golang微服务-protobuf

protobuf gRPC是一款语言中立、平台中立、开源的远程过程调用系统&#xff0c;gRPC客户端和服务端可以在多种环境中运行和交互&#xff0c;例如用java写一个服务端&#xff0c;可以用go语言写客户端调用 数据在进行网络传输的时候&#xff0c;需要进行序列化&#xff0c;序列化…

雷电模拟器安装LSPosed

雷电模拟器最新版支持LSPosed。记录一下安装过程 首先到官网下载并安装最新版&#xff0c;我安装的时候最新版是9.1.34.0&#xff0c;64位 然后开启root和系统文件读写 然后下载magisk-delta-6并安装 ,这个是吾爱破解论坛提供的&#xff0c;号称适配安卓7以上所有机型&#x…

排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

1. 插入排序 基本思想 插入排序的基本思想是将一个元素插入到已经排好序的有序表中&#xff0c;从而形成一个新的、记录数增加1的有序表。具体步骤如下&#xff1a; 将原数组分为有序数组和无序数组两部分。将数组的第一个元素视为有序数组&#xff0c;其余部分视为无序数组…