当前位置: 首页 > 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语言的创始人,以…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Spring数据访问模块设计

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

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...