当前位置: 首页 > 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;同时可以选择将 …...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

Flask RESTful 示例

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

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...

对象回调初步研究

_OBJECT_TYPE结构分析 在介绍什么是对象回调前&#xff0c;首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例&#xff0c;用_OBJECT_TYPE这个结构来解析它&#xff0c;0x80处就是今天要介绍的回调链表&#xff0c;但是先不着急&#xff0c;先把目光…...