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

[ACM学习] 动态规划基础之一二三维dp

课内学习的动态规划

有记忆的迭代

优化解的结构:原始问题的一部分解是子问题的解

三要素:1.子问题 2.状态的定义 3.状态转移方程 

定义

线性dp的一道例题

dp[i]表示以位置 i 结尾的方案总数,dp[4]=2,因为:首先只放一个4是可以的,4的位置之前还可以放1,我们不需要知道1之前还可以放什么数,只需要知道1的方案数加上4也是 dp[4] 的一部分方案数。

记得用前缀和来维护所有可行的方案。

二维dp

经验:列常常是1到结果、行常常是是否把这个选项 i 放入考虑范围

例题

首先:为什么用二维dp:对于选择,不能用一条线来解决,需要用一个从1到n的数组,来存储:把第一个选项纳入考虑(只是考虑,不是真放了),到把前 i 个纳入考虑(方便我们在上一个的基础上解决下一个) 

注意这里的列坐标是从 1 到 64 ,不是1到x,因为可以由一个比x更大的数异或 ai 后,结果是x,所以我们有必要保存比x大的数,(64的由来:每个进行异或的数大小不超过63,即11111111,所以进行异或和的结果也肯定不会超过11111111,即63)

附上代码

#include <iostream>
using namespace std;const int N = 1e5+5;
const int p = 998244353;
int dp[N][70];
int a[N];int main()
{// 请在此输入您的代码int n,x;cin >> n >> x;for(int i = 1 ; i <= n ; i++){cin >> a[i];}dp[0][0]=1;for(int i = 1 ; i <= n ; i++){for(int j = 0 ; j <= 64 ; j++){dp[i][j] = (dp[i-1][j]+dp[i-1][j^a[i]])%p;}}cout << dp[n][x];return 0;
}

注意:什么样的数字异或 ai 后是 j ?   ---  j ^ ai 这个数字(这就要用到异或 j ^ ai ^ ai = j)

三维dp例题

多一个条件就多了一个维度,来记录k次位移。

附上代码

相关文章:

[ACM学习] 动态规划基础之一二三维dp

课内学习的动态规划 有记忆的迭代 优化解的结构&#xff1a;原始问题的一部分解是子问题的解 三要素&#xff1a;1.子问题 2.状态的定义 3.状态转移方程 定义 线性dp的一道例题 dp[i]表示以位置 i 结尾的方案总数&#xff0c;dp[4]2&#xff0c;因为&#xff1a;首先只放一…...

Qt点击按钮在其附近弹出一个窗口

效果 FS_PopupWidget.h #ifndef FS_POPUPWIDGET_H #define FS_POPUPWIDGET_H#pragma once#include <QToolButton> #include <QWidgetAction> #include <QPointer>class QMenu;class FS_PopupWidget : public QToolButton {Q_OBJECTpublic:FS_PopupWidget(QW…...

Springboot注解@Configuration和@Bean注解作用,生命周期

简介&#xff1a; Configuration 类是定义 bean 配置的地方&#xff0c;而 Bean 方法是具体创建 bean 实例的方法。 Configuration 作用&#xff1a; Configuration 注解用于定义配置类&#xff0c;表明该类包含一个或多个 bean 定义的方法。Spring 容器在启动时会自动扫描这些…...

30天精通Nodejs--第十五天:Websocket

引言 这里我们将继续深入探讨另一项强大且实时性极高的网络通信技术——WebSocket。通过本篇文章,将全面了解如何在Node.js环境中利用WebSocket实现服务端与客户端之间双向、低延迟的数据传输,并掌握其基础用法以及一些高级应用场景。 基础用法 安装WebSocket库 在Node.j…...

C++深入学习之STL:2、适配器、迭代器与算法部分

适配器概述 C标准模板库(STL)中提供了几种适配器&#xff0c;这些适配器主要用于修改或扩展容器类的功能。STL中的适配器主要包括以下几种&#xff1a; 1、迭代器适配器&#xff1a;迭代器适配器提供了一种机制&#xff0c;可以将非迭代器对象转换为迭代器对象。比如back_ins…...

Tiktok/抖音旋转验证码识别

一、引言 在数字世界的飞速发展中&#xff0c;安全防护成为了一个不容忽视的课题。Tiktok/抖音&#xff0c;作为全球最大的短视频平台之一&#xff0c;每天都有数以亿计的用户活跃在其平台上。为了保护用户的账号安全&#xff0c;Tiktok/抖音引入了一种名为“旋转验证码”的安…...

【Java 设计模式】设计原则

文章目录 ✨单一职责原则&#xff08;SRP&#xff09;✨开放/封闭原则&#xff08;OCP&#xff09;✨里氏替换原则&#xff08;LSP&#xff09;✨依赖倒置原则&#xff08;DIP&#xff09;✨接口隔离原则&#xff08;ISP&#xff09;✨合成/聚合复用原则&#xff08;CARP&#…...

Druid连接池工具公式化SQL附踩坑记录

1. 需求 使用Druid连接池工具格式化sql用于回显时候美观展示 2. 代码示例 2.1 依赖 <dependency><groupId>com.alibaba</groupId><artifactId>druid</artifactId><version>1.2.6</version> </dependency> 2.2 ParseUtils…...

Linux内核--网络协议栈(二)UDP数据包发送

目录 一、引言 二、数据包发送 ------>2.1、数据发送流程 三、协议层注册 ------>3.1、socket系统调用 ------>3.2、socket创建 ------>3.3、协议族初始化 ------>3.4、对应协议的socket创建 ------>3.5、协议注册 四、通过套接字发送网络数据 --…...

基于深度学习的时间序列算法总结

1.概述 深度学习方法是一种利用神经网络模型进行高级模式识别和自动特征提取的机器学习方法&#xff0c;近年来在时序预测领域取得了很好的成果。常用的深度学习模型包括循环神经网络&#xff08;RNN&#xff09;、长短时记忆网络&#xff08;LSTM&#xff09;、门控循环单元&a…...

nginx中多个server块共用upstream会相互影响吗

背景 nginx中经常有这样的场景&#xff0c;多个server块共用一个域名。 如&#xff1a;upstream有2个以上的域名&#xff0c;nginx配置两个server块&#xff0c;共用一个upstream配置。 那么&#xff0c;如果其中一个域名发生"no live upstreams while connecting to ups…...

基于信号完整性的一些PCB设计建议

最小化单根信号线质量的一些PCB设计建议 1. 使用受控阻抗线&#xff1b; 2. 理想情况下&#xff0c;所有信号都应该使用完整的电源或地平面作为其返回路径&#xff0c;关键信号则使用地平面作为返回路径&#xff1b; 3. 信号的返回参考面发生变化时&#xff0c;在尽可能接近…...

《BackTrader量化交易图解》第8章:plot 绘制金融图

文章目录 8. plot 绘制金融图8.1 金融分析曲线8.2 多曲线金融指标8.3 Observers 观测子模块8.4 plot 绘图函数的常用参数8.5 买卖点符号和色彩风格8.6 vol 成交参数8.7 多图拼接模式8.8 绘制 HA 平均 K 线图 8. plot 绘制金融图 8.1 金融分析曲线 BackTrader内置的plot绘图函…...

什么是欧拉筛??

欧拉筛&#xff08;Eulers Sieve&#xff09;&#xff0c;又称线性筛法或欧拉线性筛&#xff0c;是一种高效筛选素数的方法。它的核心思想是从小到大遍历每个数&#xff0c;同时标记其倍数为合数&#xff0c;但每个合数只被其最小的质因数标记一次&#xff0c;从而避免了重复标…...

2023年全国职业院校技能大赛软件测试赛题—单元测试卷⑩

单元测试 一、任务要求 题目1&#xff1a;根据下列流程图编写程序实现相应处理&#xff0c;程序根据两个输入参数iRecordNum和IType计算x的值并返回。编写程序代码&#xff0c;使用JUnit框架编写测试类对编写的程序代码进行测试&#xff0c;测试类中设计最少的测试数据满足基路…...

使用WAF防御网络上的隐蔽威胁之SSRF攻击

服务器端请求伪造&#xff08;SSRF&#xff09;攻击是一种常见的网络安全威胁&#xff0c;它允许攻击者诱使服务器执行恶意请求。与跨站请求伪造&#xff08;CSRF&#xff09;相比&#xff0c;SSRF攻击针对的是服务器而不是用户。了解SSRF攻击的工作原理、如何防御它&#xff0…...

Redis基础系列-哨兵模式

Redis基础系列-哨兵模式 文章目录 Redis基础系列-哨兵模式1. 引言2. 什么是哨兵模式&#xff1f;3. 哨兵模式的配置4. 哨兵模式的启动和验证4.1 主master宕机&#xff0c;看会出现什么问题4.2 重启6379主机 5. 哨兵模式的工作原理和选举原理5.1. SDown主观下线&#xff08;Subj…...

【angular教程240112】09(完) Angular中的数据请求 与 路由

【angular教程240112】09(完) Angular中的数据请求 与 路由 目录标题 一、 Angular 请求数据简介0 使用Angular内置模块HttpClientModule和HttpClientJsonpModule:1 Angular中的GET请求:2 Angular中的POST请求:3 Angular中的JSONP请求:4使用Axios进行数据请求: 二、 详解 Angul…...

go中拷贝文件操作

一. 拷贝文件内容到另一个文件位置 // 拷贝文件内容到另一个文件里面 func copyContent() {filepath1 : "d:/abc.txt"filepath2 : "e:/eee.txt"// 读取内容data, err : os.ReadFile(filepath1) // 使用os.ReadFile函数读取指定路径的文件内容if err ! nil…...

未来气膜体育馆的发展趋势是什么?

未来气膜体育馆的发展趋势是多方面的&#xff0c;以下是其中几个方面的趋势。 起初&#xff0c;随着人们对体育运动的需求不断增加&#xff0c;气膜体育馆的建设和使用将成为一种趋势。气膜体育馆具有灵活性和可移动性的特点&#xff0c;可以快速搭建和拆除&#xff0c;能够适…...

Unity入门:从零开始认识Unity编辑器界面

Unity入门&#xff1a;从零开始认识Unity编辑器界面&#x1f4da; 本章学习目标&#xff1a;深入理解从零开始认识Unity编辑器界面的核心概念与实践方法&#xff0c;掌握关键技术要点&#xff0c;了解实际应用场景与最佳实践。本文属于《Unity工程师成长之路教程》Unity入门篇&…...

ElasticJob HTTP作业:RESTful接口调度的终极指南

ElasticJob HTTP作业&#xff1a;RESTful接口调度的终极指南 ElasticJob是ShardingSphere生态中一款分布式任务调度解决方案&#xff0c;它提供了丰富的作业类型支持&#xff0c;其中HTTP作业是实现跨系统任务调度的理想选择。通过HTTP作业&#xff0c;您可以轻松实现基于REST…...

一、ACWing笔记整理

一、基础算法1.快速排序--不稳定算法思路&#xff1a;两个指针从最左最右出发&#xff0c;当指向数<&#xff08;>&#xff09;x时向中间移动&#xff0c;若>&#xff08;<&#xff09;则两指针指向数交换#include <iostream> using namespace std;const int…...

OpenClaw多模型切换:nanobot镜像动态加载不同规格Qwen

OpenClaw多模型切换&#xff1a;nanobot镜像动态加载不同规格Qwen 1. 为什么需要动态切换模型 在本地部署AI助手时&#xff0c;我发现一个痛点&#xff1a;不同任务对模型能力的需求差异很大。简单任务如整理文件、生成周报草稿&#xff0c;用7B参数模型完全够用&#xff1b;…...

基于云平台的智能客服系统实战:架构设计与性能优化指南

最近在负责一个面向多租户的智能客服项目&#xff0c;从零到一踩了不少坑。传统单体架构的客服系统&#xff0c;一到业务高峰期就卡顿、超时&#xff0c;扩容更是噩梦。经过一番折腾&#xff0c;我们最终基于云平台构建了一套相对稳定、可扩展的解决方案。今天就把整个架构设计…...

py2exe终极指南:将Python脚本快速打包为独立Windows程序

py2exe终极指南&#xff1a;将Python脚本快速打包为独立Windows程序 【免费下载链接】py2exe Create standalone Windows programs from Python code 项目地址: https://gitcode.com/gh_mirrors/py/py2exe 你是否曾为Python程序部署而烦恼&#xff1f;想让你的Python脚本…...

上海本凡科技引领小程序开发行业,凭实力成为最受欢迎的公司

上海本凡科技在小程序开发行业中取得的成就&#xff0c;可以归结为对客户需求的深刻理解和快速响应。公司致力于构建灵活易用的小程序&#xff0c;满足不同客户的商业目标。通过持续关注市场变化和用户反馈&#xff0c;本凡科技快速调整开发策略&#xff0c;以确保其产品始终符…...

LED点阵驱动库LEDMatrix:嵌入式硬件时序控制实战指南

1. LEDMatrix 库概述&#xff1a;面向硬件驱动的二维点阵控制框架LEDMatrix 是一个专为嵌入式系统设计的轻量级 C 语言库&#xff0c;核心目标是将抽象的二维布尔数组&#xff08;bool matrix[rows][cols]&#xff09;高效、可靠地映射至物理 LED 点阵屏。其设计哲学并非通用图…...

OpenClaw:以智能之力重塑效率,轻量化进阶之路与国产创新展望

各位深耕AI领域的打工人、极客与企业管理者&#xff1a;2026年的春天&#xff0c;OpenClaw&#xff08;被全球用户亲切称为“小龙虾”&#xff09;早已成为科技圈的核心焦点&#xff0c;若你尚未接触这只席卷全球的开源AI Agent&#xff08;智能体&#xff09;框架&#xff0c;…...

禾赛年报图解:营收30亿,经调整净利5.5亿 成激光雷达行业首家全年GAAP盈利企业

雷递网 雷建平 3月24日禾赛科技&#xff08;NASDAQ:HSAI&#xff1b;HKEX:2525&#xff09;今日公布了2025年第四季度以及全年未经审计的财务数据。财报显示&#xff0c;禾赛2025年营收为30.28亿元&#xff0c;较上年同期的20.77亿元增长45.8%。禾赛2025年运营利润为1.68亿元&a…...