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

Codeforces Round 892 (Div. 2) - E. Maximum Monogonosity 思维dp 详细解析

题目链接
好久没有写题了复健一下qwq


题目大意

在这里插入图片描述


解题思路

这题目还挺妙的
首先考虑比较正常的dp, d p [ i ] [ j ] dp[i][j] dp[i][j] 为前 i i i的长度选 j j j个长度的最大价值,那么转移方程是:
图片来自:图片来源
图片来自https://www.cnblogs.com/ACMER-XiCen/p/17660694.html
但是这个是 O ( n k 2 ) O(nk^2) O(nk2)无法通过把绝对值展开进行讨论
在这里插入图片描述

  • 我们可以看到 d p [ i ] [ j ] dp[i][j] dp[i][j]其实都是由对角线上的 d p dp dp + + +几个 a a a, b b b的计算,那么我们可以把前面的部分用新的数组维护起来因为都是对角上的数值那么 i − j i-j ij是固定值那么就是 f [ 0 / 1 / 2 / 3 ] [ i − j ] f[0/1/2/3][i-j] f[0/1/2/3][ij]里面取最大值 + + +后缀部分
  • 然后因为这个虽然是对角线的上值的前 k k k里面的最大值,但是其实 d p [ i ] [ j ] > d p [ i − 1 ] [ j − 1 ] dp[i][j]>dp[i-1][j-1] dp[i][j]>dp[i1][j1]是一定成立的所以 f [ 0 / 1 / 2 / 3 ] [ i − j ] f[0/1/2/3][i-j] f[0/1/2/3][ij]只用从 k = 1 k=1 k=1转移就行
				f[0][i - j] = std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);f[1][i - j] = std::max(f[1][i - j], dp[i - 1][j - 1] + a[i] - b[i]);f[2][i - j] = std::max(f[2][i - j], dp[i - 1][j - 1] - a[i] + b[i]);f[3][i - j] = std::max(f[3][i - j], dp[i - 1][j - 1] + a[i] + b[i]);
  • 记住f数组要初始化为负无穷,不能是0
memset(f,0x80,sizeof(f));
  • 整体代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 3005;
typedef long long ll;
const ll mod = 998244353;
int a[maxn], b[maxn];
ll dp[maxn][maxn], f[4][maxn]; 
int main() {//freopen("1.txt","r",stdin);int T;scanf("%d",&T);while(T --) {int n, k;scanf("%d%d",&n,&k);memset(f,0x80,sizeof(f));// 这个0x80初始化出来是复数 for(int i = 1; i <= n; ++ i) cin >> a[i];for(int i = 1; i <= n; ++ i) cin >> b[i]; for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= k && j <= i; ++ j) {dp[i][j] = dp[i-1][j];f[0][i - j] = std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);f[1][i - j] = std::max(f[1][i - j], dp[i - 1][j - 1] + a[i] - b[i]);f[2][i - j] = std::max(f[2][i - j], dp[i - 1][j - 1] - a[i] + b[i]);f[3][i - j] = std::max(f[3][i - j], dp[i - 1][j - 1] + a[i] + b[i]);dp[i][j] = std::max(dp[i][j], f[0][i - j] + a[i] + b[i]);dp[i][j] = std::max(dp[i][j], f[1][i - j] + a[i] - b[i]);dp[i][j] = std::max(dp[i][j], f[2][i - j] - a[i] + b[i]);dp[i][j] = std::max(dp[i][j], f[3][i - j] - a[i] - b[i]);
//                for(int h = 1; h <= j; ++ h) {
//                    dp[i][j] = max(dp[i-h][j-h]+abs(a[i]-b[i-h+1])+abs(a[i-h+1]-b[i]),dp[i][j]);
//                    // printf("%d %d %lld\n",i,j,dp[i][j]);
//                }}}printf("%lld\n",dp[n][k]);} return 0;
}
  • 上面你可能会疑问这个不是抵消了吗?
f[0][i - j] = std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);
dp[i][j] = std::max(dp[i][j], f[0][i - j] + a[i] + b[i]);

注意其实这里的有个影响是 f [ 0 ] [ i − j ] f[0][i - j] f[0][ij]是包含了带 k k k的参数 所以要做两次 m a x max max, d p [ i − 1 ] [ j − 1 ] − a [ i ] − b [ i ] dp[i - 1][j - 1] - a[i] - b[i] dp[i1][j1]a[i]b[i]只是刚好这一层儿而已

相关文章:

Codeforces Round 892 (Div. 2) - E. Maximum Monogonosity 思维dp 详细解析

题目链接 好久没有写题了复健一下qwq 题目大意 解题思路 这题目还挺妙的 首先考虑比较正常的dp&#xff0c; d p [ i ] [ j ] dp[i][j] dp[i][j] 为前 i i i的长度选 j j j个长度的最大价值&#xff0c;那么转移方程是&#xff1a; 图片来自&#xff1a;图片来源 但是这个是 …...

R语言中的数据重塑

文章目录 介绍reshape2::melt()的用法实例 reshape2::dcast()的用法实例 tidyr::gather()的用法tidyr::spread()的用法 介绍 tidyverse系列包中的函数操作都是针对简洁数据框进行的&#xff0c;对于不是简洁的数据&#xff0c;实现需要进行数据重塑。数据重塑主要包括长宽表的…...

基于Java实现的社区团购系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统功能具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域…...

nodejs+vue网上婚纱购物系统elementui

便了用户足不出门也能进行购物的理念&#xff0c;方便了婚纱影楼的对商品的进一步管理,互联网成为人们快速获取、发布、和传递信息的重要渠道&#xff0c;它在人们政治、经济、生活等各个方面发挥着重要的作用。未来的时代是网络信息的时代&#xff0c;“网上生活方式”是人类今…...

【2023集创赛】加速科技杯三等奖作品:私密性高精度刷手身份认证系统

本文为2023年第七届全国大学生集成电路创新创业大赛&#xff08;“集创赛”&#xff09;加速科技杯三等奖作品分享&#xff0c;参加极术社区的【有奖征集】分享你的2023集创赛作品&#xff0c;秀出作品风采&#xff0c;分享2023集创赛作品扩大影响力&#xff0c;更有丰富电子礼…...

1500*C. Kefa and Park(dfstree)

Kefa and Park - 洛谷 Problem - 580C - Codeforces Examples input 4 1 1 1 0 0 1 2 1 3 1 4 output 2 input 7 1 1 0 1 1 0 0 0 1 2 1 3 2 4 2 5 3 6 3 7 output 2 解析&#xff1a; dfs遍历&#xff0c;记录前一个结点权值是否为1&#xff0c;并且累计路径1的个数…...

【2023保研】双非上岸东南网安

个人情况 学校&#xff1a;henu 专业&#xff1a;信息安全 排名&#xff1a;1/66 英语&#xff1a;六级500 竞赛&#xff1a;蓝桥杯PB国一&#xff0c;ISCC国一&#xff0c;密码数学挑战赛国三&#xff0c;还有其他一些省级水奖 论文&#xff1a;一篇EI在投&#xff08;三作通…...

Redis与Mybatis

作者在学习Redis整合时使用JDBC与Jedis&#xff0c;但是呢&#xff0c;现如今的环境下&#xff0c;Mybatis系列ORM框架是更受关注的方法&#xff0c;作者有一点点Mybatis基础&#xff0c;Mybatisplus几乎忘的差不多了&#xff0c;现对Redis整合Mybatis相关知识进行梳理&#xf…...

MySQL架构 InnoDB存储引擎

1. 什么是Mysql&#xff1f; 我们在开发的时候&#xff0c;我们都需要对业务数据进行存储&#xff0c;这个时候&#xff0c;你们就会用到MySQL、Oracal等数据库。 MySQL它是一个关系型数据库&#xff0c;这种关系型数据库就有Oracal、 MySQL&#xff0c;以及最近很火的PgSQL等。…...

K8S-CNI

CNI的设计思想即为:Kubernetes在启动Pod的pause容器之后&#xff0c;直接调用CNI网络插件&#xff0c;从而实现为Pod内部应用容器月在的Network Namespace配置符合预期的网络信息。 这里面需要特别关注两个方面:Container必须有自己的网络命名空间的环境&#xff0c;也就是end…...

Redis 集合类型(Set)和命令 (数据类型 四)

集合类型是一个无序、不重复的数据集合&#xff0c;它可以用于存储唯一的值&#xff0c;并提供了对集合进行交集、并集、差集等操作。 常用集合类型命令&#xff1a; 添加操作&#xff1a; sadd key member1 member2 …&#xff1a;向集合中添加一个或多个成员。 # 添加三个…...

thinkphp5 如何模拟在apifox里面 post数据接收

tp5里面控制器写的方法想直接apifox里面请求接受 必须带上这个参数 header里面 X-Requested-With&#xff1a;XMLHttpRequest...

建造者模式 创建型模式之三

想要搞清楚建造者模式&#xff0c;首先先要了解建造者模式种四个角色的定位 1.Product&#xff1a;表示被构造的复杂对象&#xff0c;就是我们要建造的东西&#xff0c;比如我们要做一个手机&#xff0c;手机就是product。 2.Builder&#xff1a;建造者&#xff0c;这里需要着…...

发布以太坊测试网络中的第一笔交易

1.安装以太坊钱包 要想发送发布以太坊测试网络中的第一笔交易&#xff0c;首先需要创建一个管理账户的钱包&#xff0c;这个钱包可以理解为管理私钥的容器&#xff0c;具体按照步骤为&#xff1a;打开Chrome浏览器应用商店搜索MetaMask&#xff0c;选择对应的钱包添加至Chrome…...

No module named ipykernel解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

Java 基于 SpringBoot 的校园疫情防控系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 文章目录 1 简介2.主要技术3 需求分析4系统设计4.1功能结构4.2 数据库设计4.2.1 数据库E/R图4.2.2 数据库表…...

windows的ui自动化测试相关

一个python第三方模块uiautomation github上也有源码&#xff0c;可以看下 uiautomation模块项目地址&#xff1a;https://github.com/yinkaisheng/Python-UIAutomation-for-Windows uiautomation模块项目地址...

Mybatis 二级缓存(使用Ehcache作为二级缓存)

上一篇我们介绍了mybatis中二级缓存的使用&#xff0c;本篇我们在此基础上介绍Mybatis中如何使用Ehcache作为二级缓存。 如果您对mybatis中二级缓存的使用不太了解&#xff0c;建议您先进行了解后再阅读本篇&#xff0c;可以参考&#xff1a; Mybatis 二级缓存https://blog.c…...

C语言 Cortex-A7核 IIC实验

iic.h #ifndef __IIC_H__ #define __IIC_H__ #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_rcc.h" /* 通过程序模拟实现I2C总线的时序和协议* GPIOF ---> AHB4* I2C1_SCL ---> PF14* I2C1_SDA ---> PF15** */#define SET_SDA_OUT do{…...

【每日一题】2769. 找出最大的可达成数字

2769. 找出最大的可达成数字 - 力扣&#xff08;LeetCode&#xff09; 给你两个整数 num 和 t 。 如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等&#xff0c;则称其为 可达成数字 &#xff1a; 每次操作将 x 的值增加或减少 1 &#xff0c;同时可以选择将 …...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...