594: Maximum Tape Utilization Ratio

解法:

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

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 和磁带的容量 m
    node 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是最小的

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

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

相关文章

流量主微信小程序工具类去水印

工具类微信小程序流量主带后台管理&#xff0c;可开通广告&#xff0c;带自有后台管理&#xff0c;不借助第三方接口 介绍 支持抖音&#xff0c;小红书&#xff0c;哔哩哔哩视频水印去除&#xff0c;功能实现不借助第三方平台。可实现微信小程序流量主广告变现功能&#xff0c…

04软件测试需求分析案例-用户登录

通读文档&#xff0c;提取信息&#xff0c;提出问题&#xff0c;整理为需求。 从需求规格说明、设计说明、配置说明等文档获取原始需求&#xff0c;通读原始需求&#xff0c;分析有哪些功能&#xff0c;每种功能要完成什么业务&#xff0c;业务该如何实现&#xff0c;业务逻辑…

DX12 快速教程(2) —— 渲染天蓝色窗口

快速导航 新建项目 "002-DrawSkyblueWindow"DirectX 12 入门1. COM 技术&#xff1a;DirectX 的中流砥柱什么是 COM 技术COM 智能指针 2.创建 D3D12 调试层设备&#xff1a;CreateDebugDevice什么是调试层如何创建并使用调试层 3.创建 D3D12 设备&#xff1a;CreateD…

《计算机组成及汇编语言原理》阅读笔记:p116-p120

《计算机组成及汇编语言原理》学习第 7 天&#xff0c;p116-p120 总结&#xff0c;总计 5 页。 一、技术总结 1.CPU优化 (1)increase overall performance number 例如&#xff1a;16位电脑提升到32位电脑。 (2)multiprocessing One way to make computers more useful i…

【蓝桥杯每日一题】12.18

&#x1f3dd;️专栏&#xff1a; 【蓝桥杯备篇】 &#x1f305;主页&#xff1a; f狐o狸x 从今天开始&#xff0c;笨狐狸&#xff0c;啊呸&#xff0c;本狐狸要开始漫长的蓝桥杯备战啦&#xff0c;将会长期更新每日一题这个专栏&#xff0c;直到蓝桥杯结束&#xff0c;各位一起…

Python 写的 智慧记 进销存 辅助 程序 导入导出 excel 可打印

图样&#xff1a; 就可以导入了 上代码 import tkinter as tk from tkinter import ttk import sqlite3 from datetime import datetime from tkinter import messagebox, filedialog import pandas as pd import reclass OrderSystem:def __init__(self, root):self.root r…

【机器学习案列】车牌自动识别系统:基于YOLO11的高效实现

&#x1f9d1; 博主简介&#xff1a;曾任某智慧城市类企业算法总监&#xff0c;目前在美国市场的物流公司从事高级算法工程师一职&#xff0c;深耕人工智能领域&#xff0c;精通python数据挖掘、可视化、机器学习等&#xff0c;发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…

SpringBoot(二)—— yaml配置文件

接上篇&#xff0c;我们对SpringBoot有了基本的了解&#xff0c;接下来探究配置文件。 目录 二、配置文件 1. SpringBoot热部署 2. 配置文件 2.1 配置文件的作用 2.2 YAML 配置文件 2.3 YAML 与 XML 比较 3. YAML语法 3.1 键值对 3.2 值的写法 3.3 对象/Map&#x…

NFV架构

通信&#xff08;CT&#xff09;的NFV技术是借鉴了IT行业的云计算概念&#xff0c;实际大规模应用在4G时代。 区别是增加了以下几点 1、NFVI是openstack的电信增强版本&#xff0c;除了nova cinder nuetru等增加了电信专用组件。 2、设计增加了mano&#xff0c;包括了VIM、NFVO…

关于Edge浏览器的设置

这里记录几条个人比较习惯的使用浏览器方式的设置&#xff0c;主要是edge浏览器 1. 黑背景色 修改整个浏览器的背景色为黑色&#xff0c;而不是主题&#xff0c;只有边框颜色改变地址栏输入edge://flags/#enable-force-dark&#xff0c;将Default 改为 Enabled&#xff1b;如…

Elasticsearch:什么是查询语言?

查询语言定义 查询语言包括数据库查询语言 (database query language - DQL)&#xff0c;是一种用于查询和从数据库检索信息的专用计算机语言。它充当用户和数据库之间的接口&#xff0c;使用户能够管理来自数据库管理系统 (database management system - DBMS) 的数据。 最广…

Android使用PorterDuffXfermode模式PorterDuff.Mode.SRC_OUT橡皮擦实现马赛克效果,Kotlin(3)

Android使用PorterDuffXfermode模式PorterDuff.Mode.SRC_OUT橡皮擦实现马赛克效果&#xff0c;Kotlin&#xff08;3&#xff09; import android.content.Context import android.graphics.Bitmap import android.graphics.BitmapFactory import android.graphics.Canvas impor…

《信管通低代码信息管理系统开发平台》Linux环境安装说明

1 简介 信管通低代码信息管理系统应用平台提供多环境软件产品开发服务&#xff0c;包括单机、局域网和互联网。我们专注于适用国产硬件和操作系统应用软件开发应用。为事业单位和企业提供行业软件定制开发&#xff0c;满足其独特需求。无论是简单的应用还是复杂的系统&#xff…

jetson Orin nx + yolov8 TensorRT 加速量化 环境配置

参考【Jetson】Jetson Orin NX纯系统配置环境-CSDN博客 一 系统环境配置&#xff1a; 1.更换源&#xff1a; sudo vi /etc/apt/sources.list.d/nvidia-l4t-apt-source.list2.更新源&#xff1a; sudo apt upgradesudo apt updatesudo apt dist-upgrade sudo apt-get updat…

Burp炮台实现(动态ip发包)

基本步骤 1.使用 zmap 爬取大量代理ip 2.使用py1脚本初步筛选可用ip 3.利用py2脚本再次筛选对目标网站可用ip&#xff08;不带payload安全检测&#xff09; 4.配置 burp 插件并加载收集到的代理池 5.加载payload&#xff0c;开始爆破 Zmap kali安装 sudo apt update apt …

springboot495基于java的物资综合管理系统的设计与实现(论文+源码)_kaic

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统物资综合管理系统信息管理难度大&#xff0c;容错率低&am…

STM32-笔记16-定时器中断点灯

一、实验目的 使用定时器 2 进行中断点灯&#xff0c;500ms LED 灯翻转一次。 二&#xff0c;定时器溢出时间计算 Tout&#xff1a;定时器溢出时间 Ft&#xff1a;定时器的时钟源频率 ARR&#xff1a;自动重装载寄存器的值 PSC&#xff1a;预分频器寄存器的值 例如&#xff0c…

【MySQL】 SQL优化讲解

一、优化前的思考 在定位到慢查询后&#xff0c;面试官常问如何优化或分析慢查询的SQL语句。若存在聚合查询、多表查询&#xff0c;可尝试优化SQL语句结构&#xff0c;如多表查询可新增临时表&#xff1b;若表数据量过大&#xff0c;可添加索引&#xff0c;但添加索引后仍慢则…

C/C++ 数据结构与算法【栈和队列】 栈+队列详细解析【日常学习,考研必备】带图+详细代码

一、介绍 栈和队列是限定插入和删除只能在表的“端点”进行的线性表&#xff0c;是线性表的子集&#xff0c;是插入和删除位置受限的线性表。 &#xff08;操作受限的线性表&#xff09; 二、栈 1&#xff09;概念&#xff1a; 栈(stack)是一个特殊的线性表&#xff0c;是限…

【HarmonyOS应用开发——ArkTS语言】购物商城的实现【合集】

目录 &#x1f60b;环境配置&#xff1a;华为HarmonyOS开发者 &#x1f4fa;演示效果&#xff1a; &#x1f4d6;实验步骤及方法&#xff1a; 1. 在src/main/ets文件中创建components文件夹并在其中创建Home.ets和HomeProduct.ets文件。​ 2. 在Home.ets文件中定义 Home 组…