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

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​的就拿整个的&#xff0c;不能拿了可以拿一部分的&#xff0c;因此可以分成0和1两种情况&#xff0c;0表示拿整个的&#xff0c;1表示还可以拿部分的&#xff0c;两种情况放在一起做一遍01背包&#xff0c;找到最大价值。 代码 #include &l…...

Temp directory ‘C:\WINDOWS\TEMP‘ does not exist

问题描述 解决方法 管理员权限问题&#xff0c;进入temp文件夹更改访问权限即可。 点击 temp文件夹 属性 -> 安全 -> 高级 -> 更改主体Users权限 给读取和写入权限 参考博客 开发springboot项目时无法启动Temp directory ‘C: \WINDOWS\TEMP‘ does not exist...

【单片机基础小知识-如何通过指针来读写寄存器】

寄存器的本质就是内存&#xff0c;RAM&#xff0c;而指针是可以对内存进行操作的&#xff0c;因此可以通过指针来读写寄存器。 如何读取以下一片地址&#xff1a; 步骤1、首地址 结构体&#xff0c;它所占用的内存空间大小与它内部成员有关。 构造一个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索引事务存储引擎

索引&#xff1a;是一个排序的列表 列表中存储的是索引的值和包含这个值数据所在行的物理地址 索引的作用 利用索引数据库可以快速定位 大大加快查询速度表的数据很大 或查询需要关联多个表 使用索引也可以查询速度加快表与表之间的连接速度使用分组和排序时可以大大减少时间提…...

【服务器使用】vscode winscp进行服务器容器连接(含修改初始密码)

1&#xff1a;获取docker的登陆信息 例如节点&#xff08;host&#xff09;、端口&#xff08;port&#xff09;、密码&#xff08;passwd&#xff09;等信息&#xff0c;这个自己找组内的前辈获取即可 2&#xff1a;配置config文件 找到vscode里面ssh处的config文件 人工找…...

Go和JavaScript结合使用:抓取网页中的图像链接

前言 在当今数字化时代&#xff0c;数据是金钱的源泉&#xff0c;对于许多项目和应用程序来说&#xff0c;获取并利用互联网上的数据是至关重要的。其中之一的需求场景是从网页中抓取图片链接&#xff0c;这在各种项目中都有广泛应用&#xff0c;特别是在动漫类图片收集项目中…...

通信协议---串口、RS232、RS485

串口 起始位&#xff1a;低电平(0) 数据位&#xff1a;通常为8位 校验位&#xff1a;数据位校验位中为1的位是奇或偶 停止位&#xff1a;高电平(1) 5V TTL电平标准 2.4V~5V&#xff1a;逻辑1; 0~0.4V:逻辑0。 图中是对字符’c’进行数据传输&#xff0c;十进制99&#xff0c;…...

UE5 c++将自定义UserWdiget添加到对应菜单栏

前言&#xff1a; 为了实现与UserWidget一致的右键添加&#xff0c;便有了此章 注&#xff1a;这里使用的是UE5.3 目标内容&#xff1a; 这里可以参考UserWidget的源码&#xff0c;拷贝一份属于自己的就ok&#xff08;本篇章只是全改成了属于自己的CommonUserWidget&#xff…...

三级缓存【又称提前暴露(early exposure)】

三级缓存是Spring框架用于解决循环依赖问题的一种机制。它用于管理正在被创建的Bean实例&#xff0c;以确保它们在适当的时候被正确初始化。三级缓存分为三个阶段&#xff0c;分别是"未暴露"、"已暴露"和"已完成"&#xff0c;以下是它们的解释&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简单查询

分层解耦的三层架构 如下图所示是手术训练系统中的实现&#xff1a; 如果你需要从new EmpServiceA()变为new EmpServiceB()&#xff0c;那么必然需要修改Service和Controller层的代码&#xff0c;那么如果我们不new 这个对象呢&#xff1f;是不是就不需要依赖Controller层。 …...

Modelsim 使用教程(5)——Analyzing Waveforms

一、概述 Wave窗口允许我们以HDL波形和数据的形式查看仿真结果。Wave窗口被划分为多个窗格。通过单击并在任意两个窗格之间拖动该条&#xff0c;可以调整路径名窗格、值窗格和波形窗格的大小。 二、加载一个设计&#xff08;Loading a Design&#xff09; 1、打开modelsim 2、…...

String-固长字符串序列

在java中&#xff0c;String不是基础数据类型&#xff0c;也不是包装器类型&#xff0c;其实它是为了便捷操作字符、字节等而诞生的引用数据类型。更多内容详见公众hao&#xff1a;云水致诚 1、String是基础数据类型吗&#xff1f; String不是基础类型&#xff0c;存储在其中的…...

RABC权限模型与Spring Security

今天&#xff0c;我将带你进入一个充满策略和刺激的领域——权限之战。在这场战斗中&#xff0c;我们的主角是RABC权限模型&#xff08;Role-Based Access Control&#xff09;和Spring Security&#xff0c;他们将共同为我们打造一个安全稳定的世界。 权限模型&#xff1a;游戏…...

linux 编译lpthread

1&#xff1a;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远程控制网关物联网应用

远程控制网关在工厂自动化领域中起到了至关重要的作用&#xff0c;特别是在工厂PLC数据通讯方面。它充当着数据传输的桥梁&#xff0c;连接了工厂中的各类设备和系统&#xff0c;实现了远程监控和控制的功能。本文将详细介绍远程控制网关在工厂PLC数据通讯中的应用。 远程控制网…...

Nginx 实现负载均衡

目录 一&#xff1a;负载均衡介绍 二、 负载均衡具备的功能 1.提高服务器性能 2.提高系统可用性 3.提高系统的可伸缩性 4.实现流量均衡 三、示例配置&#xff0c;如何使用nginx实现负载均衡 四、负载均衡策略配置 1.基于轮询的负载均衡&#xff08;默认&#…...

浅谈测试需求分析

一、什么是需求分析 小编理解的需求分析就是要弄清楚用户需要的是什么功能&#xff0c;用户会怎样使用系统。这样测试时才能更清楚的知道系统该怎么样运行&#xff0c;才能更好的设计测试用例&#xff0c;才能更好的测试。 测试需求分析是测试工作的第一步&#xff0c;经过需…...

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语言的创始人,以…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...