蓝桥杯真题:密码脱落(区间dp)

目录

题目:

解题思路:

dp分析: 

解题代码:


题目:

解题思路:

题目要求的为脱落的种子数(即回文字符中没有对应回文的字符的数量)

我们可以转换成求回文字符串最长回文字符串的长度

dp分析: 

解题代码:

#include<iostream>
#include<cstring>
using namespace std;

const int N=1e3+6;
int f[N][N];

int main(){
    string s;
    cin>>s;

    int len=s.length();

    for(int i=1;i<=len;i++){//枚举距离大小
        for(int j=0;j+i-1<len;j++){//枚举起点
            int l=j;
            int r=j+i-1;

            if(l==r) f[l][r]=1;//当距离只有一行的时候
            else{
                f[l][r]=max(f[l+1][r],f[l][r-1]);
//这里对于距离i-1的点每次因为上一次已经枚举完成,故可以直接取max

                if(s[l]==s[r]) f[l][r]=max(f[l+1][r-1]+2,f[l][r]);
//对于s[l]和s[r]相等的情况
            }
        }
    }

    cout<<len-f[0][len-1];

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/38973.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

02.MySQL——CURD

文章目录 表的增删改查Create单行数据全列插入多行数据指定列插入插入否则更新替换——REPLACE RetrieveSELECT 列WHERE 条件结果排序筛选分页结果 UpdateDelete删除数据截断表 插入查询结果聚合函数group bywhere和having SQL查询中关键字优先级函数日期函数字符串函数数学函数…

SpringBoot 统一功能的处理

SpringBoot 统一功能的处理 文章目录 SpringBoot 统一功能的处理1. 用户登录权限校验1.1 最初用户登录验证1.2 Spring AOP 统一用户登录验证的问题1.3 SpringAOP 拦截器1.3.1 实现自定义拦截器1.3.2 将自定义拦截器加入到系统配置 1.4 拦截器实现原理1.4.1 实现流程图1.4.2 实现…

快速批量改名文件!随机字母命名,让文件名更有创意!

想要让文件名更加有创意和个性化吗&#xff1f;不妨尝试使用随机字母来批量改名文件&#xff01;无论是照片、文档还是其他文件&#xff0c;只需要简单的几个步骤&#xff0c;您就可以为它们赋予一个独特的随机字母命名。这不仅可以帮助您整理文件&#xff0c;还能增加一些乐趣…

微信原生实现一个简易的图片上传功能

一、实现原理 wx.showActionSheet()&#xff1a;显示操作菜单&#xff0c;选择是从相册选择还是相机拍摄照片wx.chooseImage()&#xff1a;从本地相册选择图片或使用相机拍照。wx.uploadFile()&#xff1a;将本地资源上传到服务器。客户端发起一个 HTTPS POST 请求&#xff0c…

【微信小程序-uniapp】CustomDialog 居中弹窗组件

1. 效果图 2. 组件完整代码 <template><uni-popup :ref="ref" type="center" @change

编程小白的自学笔记十(python爬虫入门二+实例代码详解)

系列文章目录 编程小白的自学笔记九&#xff08;python爬虫入门代码详解&#xff09; 编程小白的自学笔记八&#xff08;python中的多线程&#xff09; 编程小白的自学笔记七&#xff08;python中类的继承&#xff09; 编程小白的自学笔记六&#xff08;python中类的静态方法…

一、音频基础-音频分析的重要工具(语谱图)

文章目录 1. 傅里叶转换2. 语谱图3. 应用1. 傅里叶转换 通过前面的描述可以知道,声音的本质就是各种声波,那么任意某一个时刻,都不可能是只有一个频率的波,而且声波也不可能是我们理解的标准的正弦波: 而一般我们对声音进行处理时,需要分析出频率当中的有哪些频率,然…

VScode 右键菜单加入使用用VSCode打开文件和文件夹【Windows】

VScode 右键菜单加入使用用VSCode打开文件和文件夹【Windows】 介绍修改注册表添加右键打开文件属性修改注册表添加右键打开文件夹属性修改注册表添加右键空白区域属性 介绍 鼠标右击文件或者文件夹&#xff0c;可直接用VSCode打开&#xff0c;非常方便。但如果我们在安装VSCo…

TypeScript 学习笔记(七):条件类型

条件类型 TS中的条件类型就是在类型中添加条件分支&#xff0c;以支持更加灵活的泛型&#xff0c;满足更多的使用场景。内置条件类型是TS内部封装好的一些类型处理&#xff0c;使用起来更加便利。 一、基本用法 当T类型可以赋值给U类型时&#xff0c;则返回X类型&#xff0c…

Vue 和 React 前端框架的比较

Vue 和 React 前端框架的比较 本文研究了流行的前端框架 Vue 和 React 之间的区别。通过对它们的学习曲线、视图层处理方式、组件化开发、响应式数据处理方式和生态系统及社区支持进行比较分析&#xff0c;得出了它们在不同方面的优劣和特点。该研究对于开发者在选择合适的前端…

Ceph简介及部署

Ceph Ceph一、存储基础1、单机存储设备2、Ceph 简介3、Ceph 优势5、Ceph 架构6、Ceph 核心组件7、OSD 存储后端8、Ceph 数据的存储过程9、Ceph 版本发行生命周期10、Ceph 集群部署 二、部署ceph-deploy Ceph 集群前环境配置1、关闭 selinux 与防火墙2、根据规划设置主机名3、配…

Cisco学习笔记(CCNA)——Introduction to TCP/IP

Introduction to TCP/IP 常见协议 应用层协议 协议 端口号 描述 HTTP 80 超文本传输协议&#xff0c;提供浏览网页服务 Telnet 23 远程登录协议&#xff0c;提供远程管理服务 FTP 20、21 文件传输协议&#xff0c;提供互联网文件资源共享服务 SMTP 25 简单邮件传…

【Go语言开发】简单了解一下搜索引擎并用go写一个demo

写在前面 这篇文章我们一起来了解一下搜索引擎的原理&#xff0c;以及用go写一个小demo来体验一下搜索引擎。 简介 搜索引擎一般简化为三个步骤 爬虫&#xff1a;爬取数据源&#xff0c;用做搜索数据支持。索引&#xff1a;根据爬虫爬取到的数据进行索引的建立。排序&#xf…

LayUI之增删改查

目录 一、前言 1.1 前言 1.2 前端代码(数据表格组件) 1.3 封装JS 二、LayUI增删改查的后台代码 2.1 编写Dao方法 2.1 增加 2.2 删除 2.3 修改 三、LayUI增删改查的前端代码 3.1 增加 一、前言 1.1 前言 上一篇文章我们一起做了LayUI的动态添加选项卡&#xff0c;这一篇…

【天工Godwork精品教程】天工3.1.7安装教程(附Godwork完整版下载地址)

本文讲解天工3.1.7安装过程(附Godwork完整版网盘下载地址)。 文章目录 一、天工3.1.7安装教程1. 安装GodWork-AT 3.1.72. 安装GodWork-AT 3.1.7补丁3. 安装GodWork-EOS-Setup-2017B-12314. 安装GodWork-EOS补丁5. 运行godwokr软件6. 生成ZC码7. 输入ZC码8. eos插件调用二、天…

【大数据之Hadoop】三十七、Hadoop HA高可用

1、HA概述 实现高可用最关键的策略是消除单点故障。HA分成各个组件的HA机制&#xff1a;HDFS的HA和YARN的HA。   Hadoop2.0之前&#xff0c;在HDFS集群中NameNode存在单点故障&#xff08;SPOF&#xff09;。 NameNode主要在以下两个方面影响HDFS集群&#xff1a; &#xff…

07-尚硅谷大数据技术之Spark源码

1. 环境准备&#xff08;Yarn 集群&#xff09; 搭建Spark on Yarn集群 3.3 Yarn 模式 独立部署&#xff08;Standalone&#xff09;模式由 Spark 自身提供计算资源&#xff0c;无需其他框架提供资源。这种方式降低了和其他第三方资源框架的耦合性&#xff0c;独立性非常强。但…

PyTorch训练RNN, GRU, LSTM:手写数字识别

文章目录 pytorch 神经网络训练demoResult参考来源 pytorch 神经网络训练demo 数据集&#xff1a;MNIST 该数据集的内容是手写数字识别&#xff0c;其分为两部分&#xff0c;分别含有60000张训练图片和10000张测试图片 图片来源&#xff1a;https://tensornews.cn/mnist_intr…

每日一题2023.7.19|ACM模式

文章目录 C的输入方式介绍cin>>cin.get(字符变量名)cin.get(数组名,接收字符数目)cin.get()cin.getline() getline()gets()getchar() AB问题|AB问题||AB问题|||ABⅣAB问题ⅤAB问题Ⅵ C的输入方式介绍 参考博客 cin>> 最基本&#xff0c;最常用的字符或者数字的输…