当前位置: 首页 > 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…...

从零配置YOLOv5与RealSense D405:深度测距与目标检测的完整流程指南

从零构建YOLOv5与RealSense D405的智能视觉系统&#xff1a;深度感知与目标检测实战手册 当计算机视觉遇上深度感知&#xff0c;会碰撞出怎样的火花&#xff1f;YOLOv5作为当前最流行的实时目标检测框架&#xff0c;与Intel RealSense D405深度相机结合&#xff0c;能够为机器…...

VScode 高效开发 Springboot 应用的完整指南

1. 环境准备与项目创建 第一次用VScode开发Springboot项目时&#xff0c;我对着空白编辑器发呆了半小时。后来发现只要装对插件&#xff0c;效率能翻倍。先打开VScode的扩展商店&#xff0c;这三个插件是必装的&#xff1a; Java Extension Pack&#xff1a;包含语言支持、调…...

如何让微信聊天记录真正属于你:完整备份与分析终极指南

如何让微信聊天记录真正属于你&#xff1a;完整备份与分析终极指南 【免费下载链接】WeChatMsg 提取微信聊天记录&#xff0c;将其导出成HTML、Word、CSV文档永久保存&#xff0c;对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeCh…...

告别龟速滚屏!Ubuntu 20.04下用imwheel调鼠标滚轮速度(附开机自启保姆级教程)

Ubuntu 20.04终极鼠标滚轮优化指南&#xff1a;从基础配置到系统级调优 每次在Ubuntu上浏览长网页或翻阅代码时&#xff0c;那个慢如蜗牛的滚动速度是否让你抓狂&#xff1f;作为从Windows或macOS迁移过来的用户&#xff0c;这种体验落差尤为明显。鼠标滚轮响应迟缓不仅影响工作…...

解锁Switch模拟潜能:Ryujinx架构深度解析与实战优化

解锁Switch模拟潜能&#xff1a;Ryujinx架构深度解析与实战优化 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx Ryujinx作为一款采用C#开发的开源Nintendo Switch模拟器&#xff0c;通…...

DeepChat一键启动揭秘:Llama3:8b镜像免配置部署教程(含端口自愈与模型缓存)

DeepChat一键启动揭秘&#xff1a;Llama3:8b镜像免配置部署教程&#xff08;含端口自愈与模型缓存&#xff09; 想体验一个完全私密、响应迅速、且能进行深度对话的AI助手吗&#xff1f;今天&#xff0c;我们将一起揭开DeepChat的神秘面纱。它不是一个需要复杂API密钥和网络调…...

音频标注:从原理到产业,AI听懂世界的“翻译官”

音频标注&#xff1a;从原理到产业&#xff0c;AI听懂世界的“翻译官” 引言 在人工智能的浪潮中&#xff0c;计算机视觉的“看”和自然语言处理的“读”已广为人知&#xff0c;而让机器学会“听”——理解并解析复杂的声音世界&#xff0c;正成为新的前沿。这一切的基石&…...

万物皆含意识:基于 OFIRM 框架下“信息闭合与自动确认”机制的本体论重构(声明:这是一个理论假说)

万物皆含意识&#xff1a;基于 OFIRM 框架下“信息闭合与自动确认”机制的本体论重构——对德布罗意物质波假说的对称性扩展与量子测量问题的去玄学化解作者&#xff1a;Haiting Allen Chen对应理论&#xff1a;本源场直觉共振模型 (OFIRM)___________________________________…...

数据迁移技术指南:Obsidian跨平台笔记整合解决方案

数据迁移技术指南&#xff1a;Obsidian跨平台笔记整合解决方案 【免费下载链接】obsidian-importer Obsidian Importer lets you import notes from other apps and file formats into your Obsidian vault. 项目地址: https://gitcode.com/gh_mirrors/ob/obsidian-importer …...

OpenClaw资源监控方案:Qwen3-32B镜像驱动服务器健康巡检

OpenClaw资源监控方案&#xff1a;Qwen3-32B镜像驱动服务器健康巡检 1. 为什么需要AI驱动的资源监控&#xff1f; 去年我的个人开发服务器连续宕机三次&#xff0c;每次都是因为磁盘写满导致服务崩溃。传统监控工具虽然能发出警报&#xff0c;但往往在问题发生后才会触发&…...