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

[题]宝物筛选 #单调队列优化

五、宝物筛选(洛谷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;
}

相关文章:

[题]宝物筛选 #单调队列优化

五、宝物筛选&#xff08;洛谷P1776&#xff09; 题目链接 好家伙&#xff0c;找到了一个之前学习多重背包优化时的错误…… 之前记的笔记还是很有用的…… #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帮助类 此类需要编写指定屏蔽的按键&#xff0c;灵活性差。 using System; using System.Runtime.InteropServices; using System.Diagnostics; using System.Windows.Forms; using Microsoft.Win32;namespace MyHookClass {/// <summary>/// 类一/// </su…...

Anaconda Jupyter

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言An…...

Unity中Shader的前向渲染路径ForwardRenderingPath

文章目录 前言一、前向渲染路径的特点二、渲染方式1、逐像素(效果最好)2、逐顶点(效果次之)3、SH球谐(效果最差) 三、Unity中对灯光设置 后&#xff0c;自动选择对应的渲染方式1、ForwardBase仅用于一个逐像素的平行灯&#xff0c;以及所有的逐顶点与SH2、ForwardAdd用于其他所…...

简历项目优化关键方法论-START

START方法论是非常著名的面试法则&#xff0c;经常被面试官使用的工具 Situation:情况、事情、项目需求是在什么情况下发生Task:任务&#xff0c;你负责的做的是什么Action:动作&#xff0c;针对这样的情况分析&#xff0c;你采用了什么行动方式Result:结果&#xff0c;在这样…...

TensorFlow学习1:使用官方模型进行图片分类

前言 人工智能以后会越来越发达&#xff0c;趁着现在简单学习一下。机器学习框架有很多&#xff0c;这里觉得学习谷歌的 TensorFlow&#xff0c;谷歌的技术还是很有保证的&#xff0c;另外TensorFlow 的中文文档真的很友好。 文档&#xff1a; https://tensorflow.google.cn/…...

C++ 并发编程实战 第八章 设计并发代码 一

目录 8.1 在线程间切分任务 8.1.1 先在线程间切分数据&#xff0c;再开始处理 8.1.2 以递归方式划分数据 8.1.3 依据工作类别划分任务 借多线程分离关注点需防范两大风险 在线程间按流程划分任务 8.2 影响并发性能的因素 8.2.1 处理器的数量 8.2.2 数据竞争和缓存兵乓…...

设计模式8、装饰者模式 Decorator

解释说明&#xff1a;动态地给一个对象增加一些额外的职责。就扩展功能而言&#xff0c;装饰模式提供了一种比使用子类更加灵活的替代方案 抽象构件&#xff08;Component&#xff09;&#xff1a;定义一个抽象接口以规范准备收附加责任的对象 具体构件&#xff08;ConcreteCom…...

抖音开放平台第三方代小程序开发,一整套流程

大家好&#xff0c;我是小悟 抖音小程序第三方平台开发着力于解决抖音生态体系内的小程序管理问题&#xff0c;一套模板&#xff0c;随处部署。能尽可能地减少服务商的开发成本&#xff0c;服务商只用开发一套小程序代码作为模板就可以快速批量的孵化出大量的商家小程序。 第…...

Flutter笔记:滚动之-无限滚动与动态加载的实现(GetX简单状态管理版)

Flutter笔记 无限滚动与动态加载的实现&#xff08;GeX简单状态管理版&#xff09; 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq…...

前端架构师之02_ES6_高级

1 类和继承 1.1 class类 JavaScript 语言中&#xff0c;生成实例对象的传统方法是通过构造函数。 // ES5 创建对象 // 创建一个类&#xff0c;用户名 密码 function User(name,pass){// 添加属性this.name name;this.pass pass; } // 用 原型 添加方法 User.prototype.sho…...

VScode多文件编译/调试配置

之前都是在Visual Studio写C/C&#xff0c;最近想换到VScode&#xff0c;折腾半天把launch.json和tasks.json配好了&#xff08;虽然不懂为什么&#xff0c;但确实能用了&#xff09;&#xff0c;在此做个记录。 参考资料&#xff1a;1&#xff0c;2&#xff0c;3 环境&#…...

K折交叉验证——cross_val_score函数使用说明

在机器学习中&#xff0c;许多算法中多个超参数&#xff0c;超参数的取值不同会导致结果差异很大&#xff0c;如何确定最优的超参数&#xff1f;此时就需要进行交叉验证的方法&#xff0c;sklearn给我们提供了相应的cross_val_score函数&#xff0c;可对数据集进行交叉验证划分…...

2023.09.30使用golang1.18编译Hel10-Web/Databasetools的windows版

#Go 1.21新增的 log/slog 完美解决了以上问题&#xff0c;并且带来了很多其他很实用的特性。 本次编译不使用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作为前端主流框架之一&#xff0c;因其语法接近原生JavaScript语法而广受欢迎。其生态丰富&#xff0c;常用的就有react-router、react-redux等插件&#xff0c;还有与其匹配的UI组件库antd。而且其还有用于移动端开发的react-native库&#xff0c;因此&#xff0c;react值…...

链表经典面试题(一)

面试题 1.反转链表的题目2.反转链表的图文分析3.反转链表的代码实现 1.反转链表的题目 2.反转链表的图文分析 我们在实现反转链表的时候,是将后面的元素变前面&#xff0c;前面的元素变后面&#xff0c;那么我们是否可以理解为&#xff0c;用头插法的思想来完成反转链表呢&…...

体验亚马逊的 CodeWhisperer 感觉

CodeWhisperer 是亚马逊推出的辅助编程工具&#xff0c;在程序员写代码时&#xff0c;它能根据其内容生成多种代码建议。 CodeWhisperer 目前已支持近10几种语言&#xff0c;我是用 java 语言&#xff0c;用的开发工具是 idea&#xff0c;说一下我用的情况。 亚马逊云科技开发…...

6、行内元素和块元素

6、行内元素和块元素 一、块元素 无论内容多少&#xff0c;该元素独占一行 如p标签、标题标签&#xff08;h1-h6…&#xff09; 二、行内元素 内容撑开宽度、左右都是行内元素的可以排在一行 一些元素如果能够摆放在一行都可以用行内元素&#xff0c;但是如果需要换行就需…...

LeetCode 面试题 08.01. 三步问题

文章目录 一、题目二、Java 题解 一、题目 三步问题。有个小孩正在上楼梯&#xff0c;楼梯有n阶台阶&#xff0c;小孩一次可以上1阶、2阶或3阶。实现一种方法&#xff0c;计算小孩有多少种上楼梯的方式。结果可能很大&#xff0c;你需要对结果模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__}} 查看当前…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...