[题]宝物筛选 #单调队列优化
五、宝物筛选(洛谷P1776)
题目链接
好家伙,找到了一个之前学习多重背包优化时的错误……
之前记的笔记还是很有用的……
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n, m;
int v, w, s;
int lim;
int head, tail;
struct Q{//位置, 对应的底数(base number = basenb) int pos, bn;
}q[N];//q记录的是不同mod数的组里面的底数的最大值(以及它的位置)int main(){cin >> n >> m;for(int i = 1; i <= n; i ++){scanf("%d%d%d", &w, &v, &s);//按照不超过体积的每个数作为底数//既然枚举的是组数,那么不同组之间是不会被相互影响到的。for(int modd = 0; modd < v; modd ++){head = 0, tail = -1;//数量 for(int k = 0; k * v + modd <= m; k ++){//当前位置,以及对应的底数(now base number 缩写成 nb ) int nowpos = k * v + modd, nbn = f[nowpos] - k * w;//头不在范围内了就弹出队头//不在范围内就是说:总的s的数量的体积已经无法触及到底数的对应位置了,//也就是bpos = 1,但是k = 4, s = 2,此时就是k的长度无法涉及的范围了。if(q[head].pos < k - s && head <= tail) head ++;while(q[tail].bn <= nbn && head <= tail) tail --;//队尾 ,这里的pos之前写错了……但是在某wing上还是过了……water。q[++ tail].pos = k, q[tail].bn = nbn;f[nowpos] = max(f[nowpos], q[head].bn + k * w);}}}cout << f[m];return 0;
}
相关文章:
[题]宝物筛选 #单调队列优化
五、宝物筛选(洛谷P1776) 题目链接 好家伙,找到了一个之前学习多重背包优化时的错误…… 之前记的笔记还是很有用的…… #include<bits/stdc.h> using namespace std; const int N 1e5 10; int f[N]; int n, m; int v, w, s; int l…...
.NET的键盘Hook管理类,用于禁用键盘输入和切换
一、MyHook帮助类 此类需要编写指定屏蔽的按键,灵活性差。 using System; using System.Runtime.InteropServices; using System.Diagnostics; using System.Windows.Forms; using Microsoft.Win32;namespace MyHookClass {/// <summary>/// 类一/// </su…...
Anaconda Jupyter
🙌秋名山码民的主页 😂oi退役选手,Java、大数据、单片机、IoT均有所涉猎,热爱技术,技术无罪 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 获取源码,添加WX 目录 前言An…...
Unity中Shader的前向渲染路径ForwardRenderingPath
文章目录 前言一、前向渲染路径的特点二、渲染方式1、逐像素(效果最好)2、逐顶点(效果次之)3、SH球谐(效果最差) 三、Unity中对灯光设置 后,自动选择对应的渲染方式1、ForwardBase仅用于一个逐像素的平行灯,以及所有的逐顶点与SH2、ForwardAdd用于其他所…...
简历项目优化关键方法论-START
START方法论是非常著名的面试法则,经常被面试官使用的工具 Situation:情况、事情、项目需求是在什么情况下发生Task:任务,你负责的做的是什么Action:动作,针对这样的情况分析,你采用了什么行动方式Result:结果,在这样…...
TensorFlow学习1:使用官方模型进行图片分类
前言 人工智能以后会越来越发达,趁着现在简单学习一下。机器学习框架有很多,这里觉得学习谷歌的 TensorFlow,谷歌的技术还是很有保证的,另外TensorFlow 的中文文档真的很友好。 文档: https://tensorflow.google.cn/…...
C++ 并发编程实战 第八章 设计并发代码 一
目录 8.1 在线程间切分任务 8.1.1 先在线程间切分数据,再开始处理 8.1.2 以递归方式划分数据 8.1.3 依据工作类别划分任务 借多线程分离关注点需防范两大风险 在线程间按流程划分任务 8.2 影响并发性能的因素 8.2.1 处理器的数量 8.2.2 数据竞争和缓存兵乓…...
设计模式8、装饰者模式 Decorator
解释说明:动态地给一个对象增加一些额外的职责。就扩展功能而言,装饰模式提供了一种比使用子类更加灵活的替代方案 抽象构件(Component):定义一个抽象接口以规范准备收附加责任的对象 具体构件(ConcreteCom…...
抖音开放平台第三方代小程序开发,一整套流程
大家好,我是小悟 抖音小程序第三方平台开发着力于解决抖音生态体系内的小程序管理问题,一套模板,随处部署。能尽可能地减少服务商的开发成本,服务商只用开发一套小程序代码作为模板就可以快速批量的孵化出大量的商家小程序。 第…...
Flutter笔记:滚动之-无限滚动与动态加载的实现(GetX简单状态管理版)
Flutter笔记 无限滚动与动态加载的实现(GeX简单状态管理版) 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq…...
前端架构师之02_ES6_高级
1 类和继承 1.1 class类 JavaScript 语言中,生成实例对象的传统方法是通过构造函数。 // ES5 创建对象 // 创建一个类,用户名 密码 function User(name,pass){// 添加属性this.name name;this.pass pass; } // 用 原型 添加方法 User.prototype.sho…...
VScode多文件编译/调试配置
之前都是在Visual Studio写C/C,最近想换到VScode,折腾半天把launch.json和tasks.json配好了(虽然不懂为什么,但确实能用了),在此做个记录。 参考资料:1,2,3 环境&#…...
K折交叉验证——cross_val_score函数使用说明
在机器学习中,许多算法中多个超参数,超参数的取值不同会导致结果差异很大,如何确定最优的超参数?此时就需要进行交叉验证的方法,sklearn给我们提供了相应的cross_val_score函数,可对数据集进行交叉验证划分…...
2023.09.30使用golang1.18编译Hel10-Web/Databasetools的windows版
#Go 1.21新增的 log/slog 完美解决了以上问题,并且带来了很多其他很实用的特性。 本次编译不使用log/slog 包 su - echo $GOPATH ;echo $GOROOT; cd /tmp; busybox wget --no-check-certificate https://go.dev/dl/go1.18.linux-amd64.tar.gz;\ which tar&&am…...
React简介
react作为前端主流框架之一,因其语法接近原生JavaScript语法而广受欢迎。其生态丰富,常用的就有react-router、react-redux等插件,还有与其匹配的UI组件库antd。而且其还有用于移动端开发的react-native库,因此,react值…...
链表经典面试题(一)
面试题 1.反转链表的题目2.反转链表的图文分析3.反转链表的代码实现 1.反转链表的题目 2.反转链表的图文分析 我们在实现反转链表的时候,是将后面的元素变前面,前面的元素变后面,那么我们是否可以理解为,用头插法的思想来完成反转链表呢&…...
体验亚马逊的 CodeWhisperer 感觉
CodeWhisperer 是亚马逊推出的辅助编程工具,在程序员写代码时,它能根据其内容生成多种代码建议。 CodeWhisperer 目前已支持近10几种语言,我是用 java 语言,用的开发工具是 idea,说一下我用的情况。 亚马逊云科技开发…...
6、行内元素和块元素
6、行内元素和块元素 一、块元素 无论内容多少,该元素独占一行 如p标签、标题标签(h1-h6…) 二、行内元素 内容撑开宽度、左右都是行内元素的可以排在一行 一些元素如果能够摆放在一行都可以用行内元素,但是如果需要换行就需…...
LeetCode 面试题 08.01. 三步问题
文章目录 一、题目二、Java 题解 一、题目 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。 示例1: 输入&…...
[CSCCTF 2019 Qual]FlaskLight 过滤 url_for globals 绕过globals过滤
目录 subprocess.Popen FILE warnings.catch_warnings site._Printer 这题很明显就是 SSTI了 源代码 我们试试看 {{7*7}} 然后我们就开始吧 原本我的想法是直接{{url_for.__globals__}} 但是回显是直接500 猜测过滤 我们正常来吧 {{"".__class__}} 查看当前…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
