蓝桥杯 2023 省A 更小的数

        

主要思路:

  1. 输入一个长度为n的字符串,用二维数组dp[i][j]来记录子串[i, j]是否需要反转一次才能满足条件。
  2. 使用动态规划自底向上地填充dp数组。
  3. 根据问题的要求,需要考虑字符串的子串中字符的大小关系来判断是否需要反转。
  4. 最后统计满足条件的子串的个数,即dp[i][j]为true的个数。
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    // 定义字符数组存储输入的字符串
    char s[5001];
    // 读取输入的字符串
    scanf("%s",s);
    // 获取字符串的长度
    int n=strlen(s);
    // 定义二维动态规划数组,dp[i][j]表示从i到j的子串是否需要反转一次才能满足条件
    vector<vector<bool> > dp(n,vector<bool>(n,false));

    int i,j;
    // 从字符串末尾开始向前遍历
    for(i=n-1; i>=0; i--)
    {
        // 从当前位置向后遍历字符串
        for(j=i+1; j<n; j++)
        {
            // 如果子串长度为1或2,只需比较第一个字符和最后一个字符的大小
            if(i==j-1 || i==j-2)
                dp[i][j] = s[i] > s[j] ? true : false;
            else
            {
                // 如果子串长度大于2,则需要根据动态规划的状态转移方程进行判断
                if(s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1];
                else if(s[i] > s[j])
                    dp[i][j] = true;
                else
                    dp[i][j] = false;
            }
        }
    }
    // 计数器,统计满足条件的子串个数
    int count = 0;
    // 遍历所有可能的子串
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            // 如果从i到j的子串需要反转一次才能满足条件,则计数器加1
            if(dp[i][j] == true)
                count++;
    // 输出满足条件的子串个数
    cout << count << endl;
    return 0;
}

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

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

相关文章

小红书,已破!支持无水印批量下载

在我们刷小红书时&#xff0c;经常会遇到自己喜欢的头像/壁纸/背景图图片或各大博主发布的视频教程&#xff0c;想保存下载使用和后续的查看&#xff0c;但保存下载后发现图片或视频右下角保留小红书的水印&#xff0c;很影响使用查看的体验。 所以本期文章最软库给大家分享一…

3D高斯泼溅的崛起

沉浸式媒体领域正在以前所未有的速度发展&#xff0c;其中 3D 高斯溅射成为一项关键突破。 这项技术在广泛的应用中看起来非常有前景&#xff0c;并且可能会彻底改变我们未来创建数字环境以及与数字环境交互的方式。 在本文中&#xff0c;我们将通过与摄影测量和 NeRF 等前辈进…

JAVA_会话

会话技术 1.会话: 一次会话包含多次请求和响应 2.功能: 在一次会话的范围内的多次请求&#xff0c;共享数据 3.方式: 3.1.客户端会话技术 Cookie(甜点) 1.概念: 客户端会话技术,将数据保存到客户端 2.快速入门: 1.创建Cookie对象,绑定数据new Cookie(String name,String v…

3000+人使用,这套人力资源数据分析工具还能这么用

中国科学院自动化研究所&#xff08;以下简称“自动化所”&#xff09;成立于1956年&#xff0c;是中国科学院率先布局成立的“人工智能创新研究院”的总体牵头单位&#xff0c;是中国最早开展智能科学与技术基础理论、关键技术和创新性应用研究的科研机构&#xff0c;也是中国…

G1和ZGC垃圾回收器学习

前言 ​ 随着JDK17的占有率不断升高和SpringBoot3最低支持JDk17&#xff0c;JDK17很大概率会成为大家后续升级的一个选择&#xff0c;而JDK17上最重要的垃圾回收器G1和ZGC&#xff0c;也就显得格外重要。大家提前了解或者学习一下肯定是有用的。 ​ 本篇文章也默认大家了解一…

Python 全栈体系【四阶】(十五)

第五章 深度学习 一、基本理论 1. 深度学习概述 1.1 引入 1.1.1 人工智能划时代事件 2016 年 3 月&#xff0c;Google 公司研发的 AlphaGo 以 4:1 击败世界围棋顶级选手李世石。次年&#xff0c;AlphaGo2.0 对战世界最年轻的围棋四冠王柯洁&#xff0c;以 3:0 击败对方。背后…

PCB板的叠构剖析及实际案例

PCB板可以有不同的层叠结构&#xff0c;具体取决于电路设计的要求和应用的复杂性。 以下是一些常见的PCB板叠构&#xff0c;包括单层、双层和多层PCB&#xff1a; 单层PCB&#xff08;Single-Layer PCB&#xff09;&#xff1a; 基本结构&#xff1a; 单层PCB由一个绝缘性基板组…

sqllab第二十八关通关笔记(附带28a)

知识点&#xff1a; union select 整体过滤 union all select 替换where id(输入)空格 过滤了&#xff0c;使用%09代替 经过不断的测试&#xff0c;发现原始语句为 where id(输入) 构造payload:id1)and%091(1 成功回显出了相关的信息 好&#xff0c;尝试进行错误注入 构造…

理解树的结构-算法通关村

理解树的结构-算法通关村 1.树的结构 树是一个有n个有限节点组成一个具有层次关系的集合&#xff0c;每个节点有0个或者多个子节点&#xff0c;没有父节点的节点称为根节点&#xff0c;也就是说除了根节点以外每个节点都有父节点&#xff0c;并且有且只有一个。树的种类比较多…

如何自定义异常类

如何自定义异常类 为什么要使用自定义异常类&#xff1f; 在 Java 中&#xff0c;自定义异常是指用户根据自己的需求创建的异常类。Java 提供了一些预定义的异常类&#xff0c;如 NullPointerException、ArrayIndexOutOfBoundsException 等&#xff0c;但有时这些预定义的异常…

直播预告!5位大厂测开学长学姐助力你上岸测开

大家好&#xff0c;我是洋子&#xff0c;24届春招补录&25届暑期实习招聘已经进入到白热化阶段&#xff0c;近期收到了很多同学关于求职问题的咨询&#xff0c;所以开一场公益直播来为大家答疑解惑 主题&#xff1a;校招测试开发求职如何准备&职业发展 时间&#xff1…

十二、MySQL 主从复制+高可用+读写分离

目录 一、mysqlkeeplived实现高可用LVS负载均衡 一、什么是高可用 二、为什么要用高可用 三、高可用的作用 四、keeplived 是什么&#xff1f;它用在哪里 五、安装mysql以及配置主从 六、keepalived安装 1、配置 单VIP 实现高可用 master上配置 2、backup上的配置 3、…

蓝桥杯-礼物-二分查找

题目 思路 --刚开始想到暴力尝试的方法&#xff0c;但是N太大了&#xff0c;第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s&#xff0c;在这里要能想到开一个数组来求前n个石头的总重&#xff0c;然后求前k个的直接将sum[i]-sum[i-k-1]就行了&#xff0…

@EnableConfigurationProperties注解使用

前言 当我们想把配置的内容,动态赋值到某个配置类上的时候,可以使用EnableConfigurationProperties ConfigurationProperties注解 代码准备 创建配置文件prop.properties nameada age18 email123qq.com 创建配置类 ComponentScan("com.test.pops") PropertySo…

天地一体化5G网络中LNA的辐射效应

Youssouf A S, Habaebi M H, Hasbullah N F. The radiation effect on low noise amplifier implemented in the space-aerial–terrestrial integrated 5G networks[J]. IEEE Access, 2021, 9: 46641-46651. 图2 面向卫星的5G综合网络架构方案 这篇论文《The Radiation Effect…

docker快速安装达梦数据库

docker快速安装达梦数据库 文章目录 docker快速安装达梦数据库前言环境准备下载镜像运行、配置容器 前言 因为公司需要将自己的底代码平台与客户的需求做适配&#xff0c;客户要求必须满足信创要求&#xff0c;使用达梦数据库。所以需要将原有的MySQL数据库与达梦数据库适配&a…

Android:adb命令

执行adb命令的窗口如下 Mac或Linux系统里的终端窗口&#xff1b; window系统运行输入cmd打开的指令窗口&#xff1b; Android Studio 里控制下面的Terminal窗口 1. 查看已链接的设备和模拟器 adb devices -l 2. 查看Android内核版本号 adb shell getprop ro.build.version.re…

面试笔记——Redis(集群方案:主从复制、哨兵模式和分片集群)

主从复制 在 Redis 主从集群中&#xff0c;一个主节点&#xff08;Master&#xff09;负责处理客户端的读写请求&#xff0c;而多个从节点&#xff08;Slave&#xff09;则负责复制主节点的数据&#xff0c;并对外提供读取服务——解决高并发问题。 主节点&#xff08;Master&…

vue@2.7.16 使用less、less-loader

遇到问题&#xff0c;npm install less-loader7.3.0 --save安装好less-loader后&#xff0c;执行npm run serve 项目运行不起来&#xff0c;排查后发现在安装less-loader后就提示需要安装less&#xff0c;正确的安装应如下&#xff1a; npm install less less-loader7.3.0 --sa…

了解电子元器件商城价格变动的背后逻辑

电子元器件商城价格的变动背后存在着多种逻辑和因素&#xff0c;这些因素相互交织、相互作用&#xff0c;共同影响着价格的波动。以下是一些可能存在的背后逻辑&#xff1a; 供需关系&#xff1a; 供应量变化&#xff1a;电子元器件市场的供应量受到供应商生产能力、原材料供应…