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

曲师大2023大一新生排位赛-C.String题解

C.String

题目描述

众所周知,许师哥精通字符串。
一天,许师哥意外的获得了一个字符串,但他发现这个字符串并不是一个回文串,因此他非常生气。于是他决定从这个字符串中删除若干个字符使得 剩余的字符串为一个回文串
回想回文串的定义:如果一个字符串正着读和反着读都是一样的字符串,那么这个字符串就是回文串。

输入描述

第一行有一个正整数 n\left ( 1\leq n\leq 2000 \right ),表示字符串的长度。
第二行有一个长度为 n 仅含有小写字母的字符串 s。

输出描述

输出一个整数,表示使得剩余字符串为回文串最少删除的字符数量。

样例

输入:

6
aabcaa

输出:

1

输入:

10
asdbdbdadb

输出:

3

思路:

这个题算是一个板子题,最长公共子序列问题。闫氏dp分析方法可以分析如下:

 对于这个题,我要找的是回文字符串,转化为我找字符串的正序和逆序的最长公共子序列问题

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int f[2100][2100];
int main()
{int n;cin >> n;string s1,s2;cin >> s1;s2 = s1;reverse(s2.begin(),s2.end());s1 = " " + s1;s2 = " " + s2;for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){if(s1[i] != s2[j]){f[i][j] = max(f[i - 1][j],f[i][j - 1]);}else{f[i][j] = f[i - 1][j - 1] + 1;}}}cout << n - f[n][n];
}

相关文章:

曲师大2023大一新生排位赛-C.String题解

C.String 题目描述 众所周知&#xff0c;许师哥精通字符串。 一天&#xff0c;许师哥意外的获得了一个字符串&#xff0c;但他发现这个字符串并不是一个回文串&#xff0c;因此他非常生气。于是他决定从这个字符串中删除若干个字符使得 剩余的字符串为一个回文串。 回想回文串…...

Linux Ubuntu安装RabbitMQ服务

文章目录 前言1.安装erlang 语言2.安装rabbitMQ3. 内网穿透3.1 安装cpolar内网穿透(支持一键自动安装脚本)3.2 创建HTTP隧道 4. 公网远程连接5.固定公网TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 RabbitMQ是一个在 AMQP(高级消息队列协议)基…...

什么是测试用例?如何设计?

在学习或者实际的测试工作中经常都会提到“测试用例”这个词&#xff0c;没错&#xff0c;测试用例是测试工作的核心&#xff0c;不管要做的是什么样的测试&#xff0c;在真正动手执行测试之前&#xff0c;我们都需要先根据软件需求来设计测试用例&#xff0c;之后再依据设计好…...

Maven —— 项目管理工具

前言 在这篇文章中&#xff0c;荔枝会介绍如何在项目工程中借助Maven的力量来开发&#xff0c;主要涉及Maven的下载安装、环境变量的配置、IDEA中的Maven的路径配置和信息修改以及通过Maven来快速构建项目。希望能对需要配置的小伙伴们有帮助哈哈哈哈~~~ 文章目录 前言 一、初…...

Ubuntu 命令行编辑文件后如何保存退出

在 Ubuntu 命令行中编辑文件后&#xff0c;可以使用以下步骤保存并退出&#xff1a; 按下键盘上的 Ctrl 键和 X 键组合&#xff0c;以退出编辑模式。如果文件已更改&#xff0c;你将看到提示&#xff0c;询问是否保存更改。按下 Y 键来确认保存更改&#xff0c;或按下 N 键取消…...

AHB协议理解

从小父亲就教育我&#xff0c;做一个对社会有用的人&#xff01; 目录 Chapter1 AHB Block Diagram Ginput signal lnput signals Output Signal Chapter3 Transfers AHB接口Overview Chapter6 Data Buses HWDATA HRDATA Chapter1 Introduction AHB: Advanced High-performanc…...

【UE5 多人联机教程】01-创建主界面

目录 工程地址 步骤 参考链接 工程地址 GitHub - UE4-Maple/C_MP_Lobby: 多人大厅教程项目 步骤 1. 先新建一个工程 2. 将下载的工程中的Plugins目录拷贝到自己新建的工程下 3. 打开工程&#xff0c;新建一个游戏实例 这里命名为“GI_Main” 在项目设置中设置游戏实例类为…...

HarmonyOS学习路之方舟开发框架—学习ArkTS语言(基本语法 五)

Styles装饰器&#xff1a;定义组件重用样式 如果每个组件的样式都需要单独设置&#xff0c;在开发过程中会出现大量代码在进行重复样式设置&#xff0c;虽然可以复制粘贴&#xff0c;但为了代码简洁性和后续方便维护&#xff0c;我们推出了可以提炼公共样式进行复用的装饰器St…...

React(3)

1.案例选项卡 import React, { Component } from reactexport default class App extends Component {state{tabList:[{id:1,text:"电影"},{id:2,text:"影院"},{id:3,text:"我的"}]}render() {return (<div><ul>{this.state.tabList…...

LangChain大型语言模型(LLM)应用开发(三):Chains

LangChain是一个基于大语言模型&#xff08;如ChatGPT&#xff09;用于构建端到端语言模型应用的 Python 框架。它提供了一套工具、组件和接口&#xff0c;可简化创建由大型语言模型 (LLM) 和聊天模型提供支持的应用程序的过程。LangChain 可以轻松管理与语言模型的交互&#x…...

FPGA——点亮led灯

文章目录 一、实验环境二、实验任务三、实验过程3.1 编写verliog程序3.2 引脚配置 四、仿真4.1 仿真代码4.2仿真结果 五、实验结果六、总结 一、实验环境 quartus18.1 vscode Cyclone IV开发板 二、实验任务 每间隔1S实现led灯的亮灭&#xff0c;实现流水灯的效果。 三、实…...

idea创建spark教程

1、环境准备 java -version scala -version mvn -version spark -version 2、创建spark项目 创建spark项目&#xff0c;有两种方式&#xff1b;一种是本地搭建hadoop和spark环境&#xff0c;另一种是下载maven依赖&#xff1b;最后在idea中进行配置&#xff0c;下面分别记录两…...

【JavaEE】DI与DL的介绍-Spring项目的创建-Bean对象的存储与获取

Spring的开发要点总结 文章目录 【JavaEE】Spring的开发要点总结&#xff08;1&#xff09;1. DI 和 DL1.1 DI 依赖注入1.2 DL 依赖查询1.3 DI 与 DL的区别1.4 IoC 与 DI/DL 的区别 2. Spring项目的创建2.1 创建Maven项目2.2 设置国内源2.2.1 勾选2.2.2 删除本地jar包2.2.3 re…...

C#图片处理

查找图片所在位置 原理&#xff1a;使用OpenCvSharp对比查找小图片在大图片上的位置 private static System.Drawing.Point Find(Mat BackGround, Mat Identify, double threshold 0.8) {using (Mat res new Mat(BackGround.Rows - Identify.Rows 1, BackGround.Cols - Iden…...

php 开发微信 h5 支付 APIv3 接入超详细流程

✨ 目录 &#x1f388; 申请商户号&#x1f388; 申请商户证书&#x1f388; 设置V3密钥&#x1f388; 开通H5支付&#x1f388; 设置支付域名&#x1f388; SDK 下载&#x1f388; 第一次下载平台证书&#x1f388;非第一次下载平台证书&#x1f388; H5下单 &#x1f388; 申…...

HTML学习 第一部分(前端学习)

参考学习网站: 网页简介 (w3schools.com) 我的学习思路是&#xff1a;网站实践视频。 视频很重要的&#xff0c;因为它会给你一种开阔思路的方式。你会想&#xff0c;噢&#xff01;原来还可以这样。这是书本或者网站教程 所不能教给你的。而且&#xff0c;对一些教程&#…...

python 实现串口指令通讯

上一篇文章文章写了串口数据的读取&#xff0c;这篇文章讲串口数据的写入&#xff08;指令控制&#xff09; 与下位机通信往往需要十六进制形式进行数据通信&#xff0c;根据设备串口通信指令文档进行指令通信&#xff0c;本篇以灯光控制为例&#xff1a; 1.pyserial模块封装…...

pytorch深度学习逻辑回归 logistic regression

# logistic regression 二分类 # 导入pytorch 和 torchvision import numpy as np import torch import torchvision from torch.autograd import Variable import torch.nn as nn import torch.nn.functional as F import torch.optim as optim import matplotlib.pyplot as …...

数据仓库建设-数仓分层

数据仓库能够帮助企业做出更好的决策&#xff0c;提高业务效率和效益&#xff1b;在数据仓库建设时&#xff0c;绕不开的话题就是数仓分层。 一、数据分层的好处 1. 降低数据开发成本 通用的业务逻辑加工好&#xff0c;后续的开发任务可以基于模型快速使用&#xff0c;数据需…...

共享与协作:时下最热门的企业共享网盘推荐!

现代企业面临着越来越大的数据存储和共享压力。为了提高公司的生产力和效率&#xff0c;许多企业开始寻找共享网盘解决方案。这些共享网盘平台可以帮助企业集中管理文件和数据&#xff0c;并方便快速地与同事、客户或供应商共享。以下是几款好用的企业共享网盘。 Zoho Workdriv…...

ECharts Gallery弃用后,这4个替代网站让你轻松搞定数据可视化(附优缺点对比)

ECharts Gallery弃用后&#xff0c;这4个专业级替代方案深度评测 当ECharts官方Gallery宣布停止维护时&#xff0c;许多数据可视化开发者突然失去了一个重要的灵感来源和代码参考平台。作为国内最流行的可视化库之一&#xff0c;ECharts的生态系统中其实还隐藏着多个高质量的替…...

【离线无忧】PyAutoGUI内网环境高效安装指南

1. 为什么需要离线安装PyAutoGUI&#xff1f; 最近接手了一个自动化测试项目&#xff0c;需要在完全隔离的内网环境中部署PyAutoGUI。刚开始觉得这不过是个普通的Python包&#xff0c;直到发现服务器连pip都跑不通时才意识到问题的严重性。这种场景在企业开发中其实非常常见—…...

别再乱填了!手把手教你配置Keil的IROM1和IRAM1,让STM32程序跑得更稳

深度解析Keil内存配置&#xff1a;从原理到实战的STM32开发指南 当你第一次在Keil MDK的"Target"选项卡中看到IROM1和IRAM1的配置项时&#xff0c;是否感到困惑&#xff1f;这些看似简单的地址和大小设置&#xff0c;实际上关系到整个嵌入式系统的稳定运行。许多开发…...

Qwen3.5-4B-Claude推理模型在算法面试辅导中的实战:分步推导+代码示例生成

Qwen3.5-4B-Claude推理模型在算法面试辅导中的实战&#xff1a;分步推导代码示例生成 1. 模型介绍与核心能力 Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF是一个专门针对推理任务优化的AI模型&#xff0c;它基于Qwen3.5-4B架构&#xff0c;通过蒸馏训练强化了结构化…...

从FCN到U-Net:盘点深度学习图像分割中,那些‘放大’特征图的秘密武器与选型指南

从FCN到U-Net&#xff1a;解码图像分割中的特征图放大技术选型 在构建图像分割模型时&#xff0c;特征图的上采样操作往往是决定最终分割精度的关键环节之一。不同于分类任务只需输出一个类别标签&#xff0c;分割网络需要对每个像素进行分类&#xff0c;这就要求网络能够将低分…...

从KITTI到TUM:利用evo工具链实现轨迹真值的格式转换与可视化分析

1. 理解KITTI与TUM轨迹格式的本质差异 第一次接触SLAM评估时&#xff0c;我被各种轨迹格式搞得头晕眼花。KITTI和TUM这两种最常见的格式&#xff0c;就像两个说着不同方言的技术专家。KITTI格式简单粗暴&#xff0c;直接记录12个数字代表相机的位姿变换矩阵&#xff08;去掉最后…...

3分钟掌握Balena Etcher:安全可靠的跨平台镜像烧录工具

3分钟掌握Balena Etcher&#xff1a;安全可靠的跨平台镜像烧录工具 【免费下载链接】etcher Flash OS images to SD cards & USB drives, safely and easily. 项目地址: https://gitcode.com/GitHub_Trending/et/etcher Balena Etcher是一款专为简化操作系统镜像部署…...

B站视频下载工具终极指南:3分钟快速上手,轻松保存你喜欢的每一帧画面

B站视频下载工具终极指南&#xff1a;3分钟快速上手&#xff0c;轻松保存你喜欢的每一帧画面 【免费下载链接】BiliTools A cross-platform bilibili toolbox. 跨平台哔哩哔哩工具箱&#xff0c;支持视频、音乐、番剧、课程下载……持续更新 项目地址: https://gitcode.com/G…...

飞书文档到Markdown的突破性转换技术:feishu2md架构深度解析

飞书文档到Markdown的突破性转换技术&#xff1a;feishu2md架构深度解析 【免费下载链接】feishu2md 一键命令下载飞书文档为 Markdown 项目地址: https://gitcode.com/gh_mirrors/fe/feishu2md 在当今企业协作环境中&#xff0c;飞书文档已成为团队知识沉淀的核心载体&…...

为什么90%的Python项目误用SM9?——基于NIST SP 800-56A rev3与GB/T 38635.2的合规性性能审计清单

第一章&#xff1a;SM9密码算法的合规性认知误区与审计必要性在国产密码应用推广过程中&#xff0c;SM9标识密码体系常被误认为“天然合规”——仅因列入《GB/T 38635.1—2020 信息安全技术 SM9标识密码算法 第1部分&#xff1a;总则》即等同于满足等保2.0、密评及《商用密码管…...