CF1446B Catching Cheaters 题解 DP
Catching Cheaters
传送门
题面翻译
给我们两个字符串,让我们从中选出两个字串,算出它们的最大公共子序列长度。然后将它乘 4 4 4在减去两个字串的长度。问你这个数最大是多少。
题目描述
You are given two strings A A A and B B B representing essays of two students who are suspected cheaters. For any two strings C C C , D D D we define their similarity score S ( C , D ) S(C,D) S(C,D) as 4 ⋅ L C S ( C , D ) − ∣ C ∣ − ∣ D ∣ 4\cdot LCS(C,D) - |C| - |D| 4⋅LCS(C,D)−∣C∣−∣D∣ , where L C S ( C , D ) LCS(C,D) LCS(C,D) denotes the length of the Longest Common Subsequence of strings C C C and D D D .
You believe that only some part of the essays could have been copied, therefore you’re interested in their substrings.
Calculate the maximal similarity score over all pairs of substrings. More formally, output maximal S ( C , D ) S(C, D) S(C,D) over all pairs ( C , D ) (C, D) (C,D) , where C C C is some substring of A A A , and $ D $ is some substring of B B B .
If X X X is a string, ∣ X ∣ |X| ∣X∣ denotes its length.
A string a a a is a substring of a string b b b if a a a can be obtained from b b b by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
A string a a a is a subsequence of a string b b b if a a a can be obtained from b b b by deletion of several (possibly, zero or all) characters.
Pay attention to the difference between the substring and subsequence, as they both appear in the problem statement.
You may wish to read the Wikipedia page about the Longest Common Subsequence problem.
输入格式
The first line contains two positive integers n n n and m m m ( 1 ≤ n , m ≤ 5000 1 \leq n, m \leq 5000 1≤n,m≤5000 ) — lengths of the two strings A A A and B B B .
The second line contains a string consisting of n n n lowercase Latin letters — string A A A .
The third line contains a string consisting of m m m lowercase Latin letters — string B B B .
输出格式
Output maximal S ( C , D ) S(C, D) S(C,D) over all pairs ( C , D ) (C, D) (C,D) , where C C C is some substring of A A A , and D D D is some substring of B B B .
样例 #1
样例输入 #1
4 5
abba
babab
样例输出 #1
5
样例 #2
样例输入 #2
8 10
bbbbabab
bbbabaaaaa
样例输出 #2
12
样例 #3
样例输入 #3
7 7
uiibwws
qhtkxcn
样例输出 #3
0
提示
For the first case:
abb from the first string and abab from the second string have LCS equal to abb.
The result is S ( a b b , a b a b ) = ( 4 ⋅ ∣ a b b ∣ ) − ∣ a b b ∣ − ∣ a b a b ∣ = 4 ⋅ 3 − 3 − 4 = 5 S(abb, abab) = (4 \cdot |abb|) - |abb| - |abab| = 4 \cdot 3 - 3 - 4 = 5 S(abb,abab)=(4⋅∣abb∣)−∣abb∣−∣abab∣=4⋅3−3−4=5 .
以上来自洛谷 以上来自洛谷 以上来自洛谷
解题思路
首先,暴力肯定过不了。
考虑DP。设 f i , j f_{i,j} fi,j 表示以 a i , b i a_i,b_i ai,bi 为两字串的末位的相似值(相似值计算: 4 × L C S ( A , B ) − ∣ A ∣ − ∣ B ∣ 4 \times LCS(A,B)-|A|-|B| 4×LCS(A,B)−∣A∣−∣B∣)。当 i + 1 i+1 i+1 或 j + 1 j+1 j+1 时,对 L C S ( A , B ) LCS(A,B) LCS(A,B) 无贡献,而对 ∣ A ∣ |A| ∣A∣ 或 ∣ B ∣ |B| ∣B∣ 贡献为 1 1 1,所以对相似值贡献为 ( 4 × L C S ( A ′ , B ) − ∣ A ′ ∣ − ∣ B ∣ ) − ( 4 × L C S ( ∣ A ∣ , ∣ B ∣ ) − ∣ A ∣ − ∣ B ∣ ) = ( 4 × L C S ( A , B ) − ( ∣ A ∣ + 1 ) − ∣ B ∣ ) − ( 4 × L C S ( A , B ) − ∣ A ∣ − ∣ ∣ B ) = 4 ∗ L C S ( A , B ) − ∣ A ∣ − 1 − ∣ B ∣ − 4 × L C S ( A , B ) + ∣ A ∣ + ∣ B ∣ = − 1 (4\times LCS(A',B)-|A'|-|B|)-(4\times LCS(|A|,|B|)-|A|-|B|)=(4\times LCS(A,B)-(|A|+1)-|B|)-(4\times LCS(A,B)-|A|-||B)=4*LCS(A,B)-|A|-1-|B|-4\times LCS(A,B)+|A|+|B|=-1 (4×LCS(A′,B)−∣A′∣−∣B∣)−(4×LCS(∣A∣,∣B∣)−∣A∣−∣B∣)=(4×LCS(A,B)−(∣A∣+1)−∣B∣)−(4×LCS(A,B)−∣A∣−∣∣B)=4∗LCS(A,B)−∣A∣−1−∣B∣−4×LCS(A,B)+∣A∣+∣B∣=−1,则有 f i , j = max ( f i , j , max ( f i − 1 , j , f i , j − 1 ) ) f_{i,j}=\max(f_{i,j},\max(f_{i-1,j},f_{i,j-1})) fi,j=max(fi,j,max(fi−1,j,fi,j−1))。当 i + 1 i+1 i+1 且 j + 1 j+1 j+1 的同时满足 a i + 1 = b j + 1 a_{i+1}=b_{j+1} ai+1=bj+1,则对 L C S ( A , B ) LCS(A,B) LCS(A,B) 的贡献为 4 4 4,对 ∣ A ∣ + ∣ B ∣ |A|+|B| ∣A∣+∣B∣ 的贡献为 2 2 2,所以对相似值的贡献为 ( 4 × L C S ( A ′ , B ′ ) − ∣ A ′ ∣ − ∣ B ′ ∣ ) − ( 4 × L C S ( A , B ) − ∣ A ∣ − ∣ B ∣ ) = ( 4 × ( L C S ( A , B ) + 1 ) − ( ∣ A ∣ + 1 ) − ( ∣ B ∣ + 1 ) ) − ( 4 × L C S ( A , B ) − ∣ A ∣ − ∣ B ∣ ) = ( 4 × L C S ( A , B ) + 4 − ∣ A ∣ − 1 − ∣ B ∣ − 1 ) − ( 4 × L C S ( A , B ) − ∣ A ∣ − ∣ B ∣ ) = 4 × L C S ( A , B ) + 4 − ∣ A ∣ − 1 − ∣ B ∣ − 1 − 4 × L C S ( A , B ) + ∣ A ∣ + ∣ B ∣ = 2 (4\times LCS(A',B')-|A'|-|B'|)-(4\times LCS(A,B)-|A|-|B|)=(4\times (LCS(A,B)+1)-(|A|+1)-(|B|+1))-(4\times LCS(A,B)-|A|-|B|)=(4\times LCS(A,B)+4-|A|-1-|B|-1)-(4\times LCS(A,B)-|A|-|B|)=4\times LCS(A,B)+4-|A|-1-|B|-1-4\times LCS(A,B)+|A|+|B|=2 (4×LCS(A′,B′)−∣A′∣−∣B′∣)−(4×LCS(A,B)−∣A∣−∣B∣)=(4×(LCS(A,B)+1)−(∣A∣+1)−(∣B∣+1))−(4×LCS(A,B)−∣A∣−∣B∣)=(4×LCS(A,B)+4−∣A∣−1−∣B∣−1)−(4×LCS(A,B)−∣A∣−∣B∣)=4×LCS(A,B)+4−∣A∣−1−∣B∣−1−4×LCS(A,B)+∣A∣+∣B∣=2,由此可得此时 f i , j = f i − 1 , j − 1 + 2 f_{i,j}=f_{i-1,j-1}+2 fi,j=fi−1,j−1+2。
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 5000 + 5;
int n, m;
char s1[Maxn], s2[Maxn];
int f[Maxn][Maxn];
int ans;
inline void work() {cin >> n >> m >> s1 + 1 >> s2 + 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {f[i][j] = max(f[i][j], max(f[i][j - 1], f[i - 1][j]) - 1);if (s1[i] == s2[j]) {f[i][j] = f[i - 1][j - 1] + 2;}ans = max(ans, f[i][j]);}}cout << ans << endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;
}
还不会?看这里。
相关文章:
CF1446B Catching Cheaters 题解 DP
Catching Cheaters 传送门 题面翻译 给我们两个字符串,让我们从中选出两个字串,算出它们的最大公共子序列长度。然后将它乘 4 4 4在减去两个字串的长度。问你这个数最大是多少。 题目描述 You are given two strings A A A and B B B representin…...
用python实现文本/图片生成视频
使用Python来生成视频通常涉及到使用一些专门的库,比如 OpenCV 或者 moviepy。下面是一个简单的例子,使用OpenCV和PIL(Python Imaging Library)来创建一个视频。 python复制代码 import cv2 import numpy as np from PIL import …...
Android Gradle Plugin、Gradle、Android Studio版本关系
参考链接 Android Gradle Plugin 与 gradle 对应关系 插件版本所需的最低 Gradle 版本8.38.48.28.28.18.08.08.07.47.57.37.47.27.3.37.17.27.07.04.2.06.7.14.1.06.54.0.06.1.13.6.0 - 3.6.45.6.43.5.0 - 3.5.45.4.13.4.0 - 3.4.35.1.13.3.0 - 3.3.34.10.13.2.0 - 3.2.14.63…...

PyTorch深度学习实战(30)——Deepfakes
PyTorch深度学习实战(30)——Deepfakes 0. 前言1. Deepfakes 原理2. 数据集分析3. 使用 PyTorch 实现 Deepfakes3.1 random_warp.py3.2 Deepfakes.py 小结系列链接 0. 前言 Deepfakes 是一种利用深度学习技术生成伪造视频和图像的技术。它通过将一个人的…...
java 修改JsonObject对象所有的Value类型为String
将JSONObject 或者JSONArray 中所有Value 为数值类型 转为String. 转换前: [{"zjlx": 201,"xm": "刘**","cbdjxxlist": [{"zspmdm": 102031201,"rybm": "43000010300000411195","jfrlx": 1…...
Vue3-47-Pinia-修改全局状态变量值的方式
说明 修改全局状态变量的值,是一个比较常规而且常见的操作。 本文就介绍四种常见的操作。 由于Option Store 和Setup Store 在修改的时候略有不同,所以本文也会将不同点体现一下。 全局状态变量的定义 包含了 Option Store 和Setup Store 两种定义方式&a…...

【Scala】——面向对象
1 Scala 包 1.1 包风格 Scala 有两种包的管理风格。 第一种 Java 的包管理风格相同,每个源文件一个包(包 名和源文件所在路径不要求必须一致),包名用“.”进行分隔以表示包的层级关系,如 com.atguigu.scala。另一种风…...
【MediaFoundation】OpenCV VideoCapture 读取音频源码
OpenCV 读取音频代码实例 在windows7 以及OpenCV4 过后可以使用 CAP_MSMF 读取音频,但是OpenCV没有播放音频的API。代码示例如下。 本文解析OpenCVCAP_MSMF 进行文件、设备的 音频读取,学习MediaFoundation 的使用。 #include <opencv2/core.hpp>…...
2024秋招,百度测试开发工程师一面
前言 大家好,今天我来回顾一下秋招中的一场很重要技术面试 一面面试官深挖我的项目经历,并提出了很多的实际场景,我现在回顾依然有很多新的认识 过程 自我介绍实习工作中,做得最好的地方是什么? 我先介绍了一下实习…...

Git 使用与问题记录 二(公司快速上手版)
写在前面 记录自己学习的内容,方便后面忘记的时候查看。给像我一样的新手提供一点参考 正文 上一章已经安装好了Git,如何使用呢。我这里会分享两种办法,第一种是在VS2022中克隆代码,修改和提交;第二种是用命令提交。…...

【C语言小游戏】贪吃蛇
文章目录 1.引言2.运行图2.涉及知识3 Windows API3.1 控制台3.2 控制台屏幕坐标3.3 操作句柄3.4 控制台屏幕光标3.5 监视按键 4. 设计说明5. 完整代码 1.引言 使⽤C语⾔在Windows环境的控制台中模拟实现经典⼩游戏贪吃蛇 实现基本的功能: 贪吃蛇地图绘制蛇吃⻝物的…...

价值7500的在线授权网站源码支持IP+域名+双向授权全开源
PHP授权验证更新系统完整版,一键更新系统,一键卡密生成自助授权功能,域名ip双重验证功能等等 修复盗版检测,确保实时查看盗版 修复在线加密系统,一键加密 授权系统几乎所有的程序都能整合使用,包括您的app和计算机程序…...
haiku实现门控多头注意力模块
在多头注意力机制中,通常输入的数据包括查询(Q)、键(K)和值(V)。这些数据的维度以及权重矩阵的维度在多头注意力机制中扮演关键角色。下面对数据及权重的维度进行解释: 输入数据&…...
【React 常用的 TS 类型】持续更新
1)定义样式的 TS 类型 【 React.CSSProperties 】 一般定义样式时需要的类型限制,如下: const customStyle: React.CSSProperties {color: blue,fontSize: 16px,margin: 10px,}; 2)定义 Input Ref 属性时的 TS 类型限制 【 R…...

打破传统边界,VR技术与六西格玛设计理念的创新融合!
在科技飞速发展的今天,虚拟现实(VR)技术以其独特的沉浸式体验,正在改变我们的生活和工作方式。然而,要让VR真正成为主流,我们必须解决一些关键问题,其中最重要的就是用户体验。六西格玛设计&…...

[uniapp] uni-ui+vue3.2小程序评论列表组件 回复评论 点赞和删除
先看效果 下载地址 uni-app官方插件市场: cc-comment组件 环境 基于vue3.2和uni-ui开发; 依赖版本参考如下: "dependencies": {"dcloudio/uni-mp-weixin": "3.0.0-3090820231124001","dcloudio/uni-ui": "^1.4.28","…...
TongLINKQ(3):TongLINKQ常用命令
启动: tlq 暂停: tlq -cabort -y -w1 查看lic信息: tlqstat –lic 查看队列消息: tlqstat -qcu qcu名 -c 查看发送连接状态: tlqstat -snd qcu名 -1 -ct 1 查看指定的Qcu连接状态: tlqsta…...
抽水马桶出水慢解决记录
今天分享一些修马桶的小心得(雾) 家里的马桶出水很好,但是水却不怎么被冲下去(出水很慢),这会导致内容物滞留,造成很不好的使用体验。 出于成本考虑,首先选择自己维修。 首先直接…...
img标签的奇怪问题
本来只是为实现一个轮播图,img的url地址是从后端接口获取的,但不巧的是url地址的图片都过期了。 因为懒得重新到网上找图,就想直接用一下本地的图片,简单的想法遇到一堆问题。 问题一: 因为是springboot项目…...

深入探究Hibernate:优雅、强大的Java持久化框架
目录 1、前言 2、Hibernate简介 2.1 什么是Hibernate 2.2 为什么选择Hibernate 3、Hibernate核心概念 3.1 实体类和映射文件 3.2 数据库表和持久化类的映射 3.3 主键生成策略 3.4 持久化操作 3.5 查询语言(HQL和Criteria) 3.6 事务管理 4、Hibernate配置与连接 4…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...