2022 icpc杭州站 C. No Bug No Game - 背包dp
题面
分析
能拿整个 p i p_i pi的就拿整个的,不能拿了可以拿一部分的,因此可以分成0和1两种情况,0表示拿整个的,1表示还可以拿部分的,两种情况放在一起做一遍01背包,找到最大价值。
代码
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 3010;int dp[N][N][2];
int w[N][20];
int p[N];signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;int sum = 0;for(int i = 1; i <= n; i ++) {cin >> p[i];sum += p[i];for(int j = 1; j <= p[i]; j ++) cin >> w[i][j];}if(sum <= m) {int ans = 0;for(int i = 1; i <= n; i ++) ans += w[i][p[i]];cout << ans << "\n";return 0;}memset(dp, -0x3f, sizeof dp);dp[0][0][0] = 0;for(int i = 1; i <= n; i ++) {for(int j = 0; j <= m; j ++) {dp[i][j][0] = dp[i - 1][j][0];dp[i][j][1] = dp[i - 1][j][1];if(j >= p[i]) {dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - p[i]][0] + w[i][p[i]]);dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - p[i]][1] + w[i][p[i]]);}for(int k = 1; k < p[i]; k ++) {if(j >= k) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k][0] + w[i][k]);}}}cout << max(dp[n][m][0], dp[n][m][1]) << "\n";
}
相关文章:
2022 icpc杭州站 C. No Bug No Game - 背包dp
题面 分析 能拿整个 p i p_i pi的就拿整个的,不能拿了可以拿一部分的,因此可以分成0和1两种情况,0表示拿整个的,1表示还可以拿部分的,两种情况放在一起做一遍01背包,找到最大价值。 代码 #include &l…...
Temp directory ‘C:\WINDOWS\TEMP‘ does not exist
问题描述 解决方法 管理员权限问题,进入temp文件夹更改访问权限即可。 点击 temp文件夹 属性 -> 安全 -> 高级 -> 更改主体Users权限 给读取和写入权限 参考博客 开发springboot项目时无法启动Temp directory ‘C: \WINDOWS\TEMP‘ does not exist...
【单片机基础小知识-如何通过指针来读写寄存器】
寄存器的本质就是内存,RAM,而指针是可以对内存进行操作的,因此可以通过指针来读写寄存器。 如何读取以下一片地址: 步骤1、首地址 结构体,它所占用的内存空间大小与它内部成员有关。 构造一个28字节的类型 type…...
CountDownTimer倒计时使用
CountDownTimer倒计时使用 CountDownTimer使用 CountDownTimer 代码片. // An highlighted blockprivate MyCountDownTimer timer;private final long TIME 7 * 1000L;private final long INTERVAL 1000L;private class MyCountDownTimer extends CountDownTimer{/*** p…...
MySQL索引事务存储引擎
索引:是一个排序的列表 列表中存储的是索引的值和包含这个值数据所在行的物理地址 索引的作用 利用索引数据库可以快速定位 大大加快查询速度表的数据很大 或查询需要关联多个表 使用索引也可以查询速度加快表与表之间的连接速度使用分组和排序时可以大大减少时间提…...
【服务器使用】vscode winscp进行服务器容器连接(含修改初始密码)
1:获取docker的登陆信息 例如节点(host)、端口(port)、密码(passwd)等信息,这个自己找组内的前辈获取即可 2:配置config文件 找到vscode里面ssh处的config文件 人工找…...
Go和JavaScript结合使用:抓取网页中的图像链接
前言 在当今数字化时代,数据是金钱的源泉,对于许多项目和应用程序来说,获取并利用互联网上的数据是至关重要的。其中之一的需求场景是从网页中抓取图片链接,这在各种项目中都有广泛应用,特别是在动漫类图片收集项目中…...
通信协议---串口、RS232、RS485
串口 起始位:低电平(0) 数据位:通常为8位 校验位:数据位校验位中为1的位是奇或偶 停止位:高电平(1) 5V TTL电平标准 2.4V~5V:逻辑1; 0~0.4V:逻辑0。 图中是对字符’c’进行数据传输,十进制99,…...
UE5 c++将自定义UserWdiget添加到对应菜单栏
前言: 为了实现与UserWidget一致的右键添加,便有了此章 注:这里使用的是UE5.3 目标内容: 这里可以参考UserWidget的源码,拷贝一份属于自己的就ok(本篇章只是全改成了属于自己的CommonUserWidgetÿ…...
三级缓存【又称提前暴露(early exposure)】
三级缓存是Spring框架用于解决循环依赖问题的一种机制。它用于管理正在被创建的Bean实例,以确保它们在适当的时候被正确初始化。三级缓存分为三个阶段,分别是"未暴露"、"已暴露"和"已完成",以下是它们的解释&a…...
【ARM Coresight 系列文章 3.5 - ARM Coresight -- JTAG-DP(JTAG Debug Port) 详细介绍】
请阅读【ARM Coresight SoC-400/SoC-600 专栏导读】 文章目录 概述1.1 DP elements1.1.1 外部连接到 JTAG-DP上的信号1.1.2 Debug TAP 状态机1.2 指令扫描链和指令1.3 DPv3 JTAG-DP 访问AP示意图概述 本节内容主要介绍 JTAG Debug Port 、Debug Test Access Port (DBGTAP), D…...
【笔记】回顾JavaWeb结合自身开发的项目——分层解耦与IOC、MySQL简单查询
分层解耦的三层架构 如下图所示是手术训练系统中的实现: 如果你需要从new EmpServiceA()变为new EmpServiceB(),那么必然需要修改Service和Controller层的代码,那么如果我们不new 这个对象呢?是不是就不需要依赖Controller层。 …...
Modelsim 使用教程(5)——Analyzing Waveforms
一、概述 Wave窗口允许我们以HDL波形和数据的形式查看仿真结果。Wave窗口被划分为多个窗格。通过单击并在任意两个窗格之间拖动该条,可以调整路径名窗格、值窗格和波形窗格的大小。 二、加载一个设计(Loading a Design) 1、打开modelsim 2、…...
String-固长字符串序列
在java中,String不是基础数据类型,也不是包装器类型,其实它是为了便捷操作字符、字节等而诞生的引用数据类型。更多内容详见公众hao:云水致诚 1、String是基础数据类型吗? String不是基础类型,存储在其中的…...
RABC权限模型与Spring Security
今天,我将带你进入一个充满策略和刺激的领域——权限之战。在这场战斗中,我们的主角是RABC权限模型(Role-Based Access Control)和Spring Security,他们将共同为我们打造一个安全稳定的世界。 权限模型:游戏…...
linux 编译lpthread
1:undefined reference to pthread_create gcc main.c -o test -lpthread [roothqgao ddserver]# gcc ddserver.c -o ddserver -lpthread [roothqgao ddserver]# ./ddserver Segmentation fault makefile 简单例子 all: httpd client LIBS -lpthread #-lsocket h…...
工业自动化工厂PLC远程控制网关物联网应用
远程控制网关在工厂自动化领域中起到了至关重要的作用,特别是在工厂PLC数据通讯方面。它充当着数据传输的桥梁,连接了工厂中的各类设备和系统,实现了远程监控和控制的功能。本文将详细介绍远程控制网关在工厂PLC数据通讯中的应用。 远程控制网…...
Nginx 实现负载均衡
目录 一:负载均衡介绍 二、 负载均衡具备的功能 1.提高服务器性能 2.提高系统可用性 3.提高系统的可伸缩性 4.实现流量均衡 三、示例配置,如何使用nginx实现负载均衡 四、负载均衡策略配置 1.基于轮询的负载均衡(默认&#…...
浅谈测试需求分析
一、什么是需求分析 小编理解的需求分析就是要弄清楚用户需要的是什么功能,用户会怎样使用系统。这样测试时才能更清楚的知道系统该怎么样运行,才能更好的设计测试用例,才能更好的测试。 测试需求分析是测试工作的第一步,经过需…...
18、Python的编码规范:PEP 8介绍及基本遵循原则
文章目录 PEP 8简介基本遵循原则1. 缩进2. 行宽3. 空行4. 导入5. 空格6. 命名约定7. 表达式和语句中的空格8. 注释9. 编码声明10. 文档字符串PEP 8简介 PEP 8,或Python Enhancement Proposal 8,是一个官方文档,发布于2001年。它由Guido van Rossum,Python语言的创始人,以…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
麒麟系统使用-进行.NET开发
文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的,如果需要进行.NET开发,则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET,所以要进…...
第22节 Node.js JXcore 打包
Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本,基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...
