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个长度的最大价值,那么转移方程是:
图片来自:图片来源
但是这个是 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 i−j是固定值那么就是 f [ 0 / 1 / 2 / 3 ] [ i − j ] f[0/1/2/3][i-j] f[0/1/2/3][i−j]里面取最大值 + + +后缀部分
- 然后因为这个虽然是对角线的上值的前 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[i−1][j−1]是一定成立的所以 f [ 0 / 1 / 2 / 3 ] [ i − j ] f[0/1/2/3][i-j] f[0/1/2/3][i−j]只用从 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][i−j]是包含了带 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[i−1][j−1]−a[i]−b[i]只是刚好这一层儿而已
相关文章:
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个长度的最大价值,那么转移方程是: 图片来自:图片来源 但是这个是 …...
R语言中的数据重塑
文章目录 介绍reshape2::melt()的用法实例 reshape2::dcast()的用法实例 tidyr::gather()的用法tidyr::spread()的用法 介绍 tidyverse系列包中的函数操作都是针对简洁数据框进行的,对于不是简洁的数据,实现需要进行数据重塑。数据重塑主要包括长宽表的…...
基于Java实现的社区团购系统设计与实现(源码+lw+部署文档+讲解等)
文章目录 前言系统功能具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序(小蔡coding)有保障的售后福利 代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域…...
nodejs+vue网上婚纱购物系统elementui
便了用户足不出门也能进行购物的理念,方便了婚纱影楼的对商品的进一步管理,互联网成为人们快速获取、发布、和传递信息的重要渠道,它在人们政治、经济、生活等各个方面发挥着重要的作用。未来的时代是网络信息的时代,“网上生活方式”是人类今…...
【2023集创赛】加速科技杯三等奖作品:私密性高精度刷手身份认证系统
本文为2023年第七届全国大学生集成电路创新创业大赛(“集创赛”)加速科技杯三等奖作品分享,参加极术社区的【有奖征集】分享你的2023集创赛作品,秀出作品风采,分享2023集创赛作品扩大影响力,更有丰富电子礼…...
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 解析: dfs遍历,记录前一个结点权值是否为1,并且累计路径1的个数…...
【2023保研】双非上岸东南网安
个人情况 学校:henu 专业:信息安全 排名:1/66 英语:六级500 竞赛:蓝桥杯PB国一,ISCC国一,密码数学挑战赛国三,还有其他一些省级水奖 论文:一篇EI在投(三作通…...
Redis与Mybatis
作者在学习Redis整合时使用JDBC与Jedis,但是呢,现如今的环境下,Mybatis系列ORM框架是更受关注的方法,作者有一点点Mybatis基础,Mybatisplus几乎忘的差不多了,现对Redis整合Mybatis相关知识进行梳理…...
MySQL架构 InnoDB存储引擎
1. 什么是Mysql? 我们在开发的时候,我们都需要对业务数据进行存储,这个时候,你们就会用到MySQL、Oracal等数据库。 MySQL它是一个关系型数据库,这种关系型数据库就有Oracal、 MySQL,以及最近很火的PgSQL等。…...
K8S-CNI
CNI的设计思想即为:Kubernetes在启动Pod的pause容器之后,直接调用CNI网络插件,从而实现为Pod内部应用容器月在的Network Namespace配置符合预期的网络信息。 这里面需要特别关注两个方面:Container必须有自己的网络命名空间的环境,也就是end…...
Redis 集合类型(Set)和命令 (数据类型 四)
集合类型是一个无序、不重复的数据集合,它可以用于存储唯一的值,并提供了对集合进行交集、并集、差集等操作。 常用集合类型命令: 添加操作: sadd key member1 member2 …:向集合中添加一个或多个成员。 # 添加三个…...
thinkphp5 如何模拟在apifox里面 post数据接收
tp5里面控制器写的方法想直接apifox里面请求接受 必须带上这个参数 header里面 X-Requested-With:XMLHttpRequest...
建造者模式 创建型模式之三
想要搞清楚建造者模式,首先先要了解建造者模式种四个角色的定位 1.Product:表示被构造的复杂对象,就是我们要建造的东西,比如我们要做一个手机,手机就是product。 2.Builder:建造者,这里需要着…...
发布以太坊测试网络中的第一笔交易
1.安装以太坊钱包 要想发送发布以太坊测试网络中的第一笔交易,首先需要创建一个管理账户的钱包,这个钱包可以理解为管理私钥的容器,具体按照步骤为:打开Chrome浏览器应用商店搜索MetaMask,选择对应的钱包添加至Chrome…...
No module named ipykernel解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...
Java 基于 SpringBoot 的校园疫情防控系统
博主介绍:✌程序员徐师兄、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上也有源码,可以看下 uiautomation模块项目地址:https://github.com/yinkaisheng/Python-UIAutomation-for-Windows uiautomation模块项目地址...
Mybatis 二级缓存(使用Ehcache作为二级缓存)
上一篇我们介绍了mybatis中二级缓存的使用,本篇我们在此基础上介绍Mybatis中如何使用Ehcache作为二级缓存。 如果您对mybatis中二级缓存的使用不太了解,建议您先进行了解后再阅读本篇,可以参考: 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. 找出最大的可达成数字 - 力扣(LeetCode) 给你两个整数 num 和 t 。 如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等,则称其为 可达成数字 : 每次操作将 x 的值增加或减少 1 ,同时可以选择将 …...
开源电子合同签署平台小程序源码 在线签署电子合同小程序源码 合同在线签署源码
聚合市场上各类电子合同解决方案商,你无需一个一个的对接电子合同厂商, 费时,费力,因为这个工作我们已经做了适配,你只需要一个接口就能使用我们的所有服务商, 同时你还可以享受我们的接口渠道价格。 Mini-…...
36 二叉树中序遍历
二叉树中序遍历 题解1 递归题解2 迭代 给定一个二叉树的根节点 root ,返回它的 中序 遍历 。 提示: 树中节点数目在范围 [0, 100] 内-100 < Node.val < 100 进阶: 递归算法很简单,你可以通过迭代算法完成吗? 题解1 递归…...
广州华锐互动:VR结绳逃生训练模拟真实火灾场景,增强训练沉浸感
随着科技的发展,虚拟现实(VR)技术已被广泛应用到各个领域,其中包括消防训练。VR消防结绳训练是一种创新的消防训练方式,它通过虚拟现实技术模拟真实的灭火场景,使消防人员能够在无风险的环境中进行高强度的…...
Flink安装及简单使用
目录 转载处(个人用最新1.17.1测试) 依赖环境 安装包下载地址 Flink本地模式搭建 安装 启动集群 查看WebUI 停止集群 Flink Standalone搭建 安装 修改flink-conf.yaml配置文件 修改workers文件 复制Flink安装文件到其他服务器 启动集群 查…...
QT信号槽
目录 信号槽的概念 按钮的常用信号 自定义槽函数 自定义信号函数 自定义槽和信号注意的事项 信号与槽的拓展 lambda表达式 信号槽的概念 信号槽是Qt框架引以为豪的机制之一。所谓信号槽,实际就是观察者模式。当某个事件发生之后,比如,…...
Spring Boot 技术架构图(InsCode AI 创作助手辅助)
Spring Boot 技术架构是一种用于构建现代应用程序的框架,它可以与各种前端、代理、网关、业务服务、中间件、存储、持续集成和容器服务集成在一起,以创建功能强大的应用程序。 源文件下载链接!!!!ÿ…...
python使用mitmproxy和mitmdump抓包在手机上抓包(三)
现在手机的使用率远超过电脑,所以这篇记录用mitmproxy抓手机包,实现手机流量监控。 环境:win10 64位,Python 3.10.4,雷电模拟器4.0.78,android版本7.1.2(设置-拉至最底部-关于平板电脑…...
react create-react-app v5 从零搭建(使用 npm run eject)
前言: 好久没用 create-react-app做项目了,这次为了个h5项目,就几个页面,决定自己搭建一个(ps:mmp 好久没用,搭建的时候遇到一堆问题)。 我之前都是使用 umi 。后台管理系统的项目 使用 antd-…...
在微信小程序中跳转到另一个小程序(多种实现方式)
方式一: 配置要跳转的appid和小程序页面路径 wx.navigateToMiniProgram({appId: 目标小程序appid,path: 目标小程序页面路径,//develop开发版;trial体验版;release正式版envVersion: release, success(res) {// 打开成功console.log("跳…...
beanstalkd 启动跟停止【经常使用 nohup 和 配合来启动程序,如: nohup ./test 同时免疫SIGINT和SIGHUP信号】
启动命令: nohup /usr/bin/beanstalkd -l 0.0.0.0 -p 11300 & >> /dev/null 2>&1 正常启动后,利用 【lsof -i:11300】查看 该服务是否正常启动 停止命令: /etc/init.d/beanstalkd stop 正常停止后,利用 【l…...
网站建设教程学校/凡科建站教程
使用exists函数和嵌套子查询,在大多数情况下使用exists函数而不是使用IN函数(子结果很大用exists,很小用in)。使用/*materialize*/with as 物化部分查询,避免展开产生误差执行计划。巧用分析函数,较少表的访…...
建设部指定招标网站/seo培训赚钱
上次了解了一些DesiredCapabilities的用法,有些还是不太清楚,去appium官网找了找官方文档,觉得写的很全:## Appium 服务关键字<expand_table>|关键字|描述|实例| |----|-----------|-------| |automationName|你想使用的自动化测试引擎…...
用二级域名做的网站算新站吗/域名购买
题目: 小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。 魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x1个魔法币 魔法机器2:如果投入x…...
自己做物流网站/域名买卖交易平台
在本文中,我将向你展示如何使用ASP.NET AJAX框架对添加可点击的热点的HTML Map控件进行扩展。经扩展后,当我们的鼠标移动到这些热点上后,即弹出关于这些热点的详细信息;但是,这些详细信息都是通过AJAX异步方式从远程服务中取得的。…...
英文搜索网站/app拉新项目推广代理
一、下载consul 地址:https://www.consul.io/downloads.html 二、解压到目录:C:\Tool\Consul (可任意目录) 三、在path中添加环境变量: 四、测试>在cmd中输入:consul 结果如下图便说明成功 五、启动:consul agent -dev -u…...
网站主机免费/网站建设需求模板
一:打破狭窄的技术视野 ①真实项目对外开发系统性讲解 ②例如电商、教育行业、社区网站等主流互联网场景的商业解决方案讲解 ③针对不同业务场景海量数据或者访问量以及及时响应等所面临的挑战进行对应的瓶颈分析。 ④拓展技术视野,与一线大厂零距离…...