[蓝桥杯 2023 省 A] 更小的数(dp基础应用)

embedded/2024/9/19 4:59:47/ 标签: 蓝桥杯, dp, 算法, 字符串

来源

洛谷P9232

dp_2">本题dp思想

dp主要思想是:在同一类问题模型下,依赖于已经解决的简单问题基础上,用很小的代价获得更复杂一点的问题的解决方案。
有的题的DP是在下标上顺序性递推的,类似于dp[i]=dp[i-1]+something;
然而这道题的DP是在子串长度上的顺序性递推,而不是在下标上的顺序性递推。

过程

首先算出所有长度为2的子串的dp值,即所有的dp[i][i+1],然后长度依次从3,4,……递增到n,每一个区间从i到j的子串,他们的dp值意味着可否反转这一段的子串,dp=0不可翻转,dp=1可翻转。

对于长度为len的子串,左右下标分别为i和j

d p ( i , j ) = { 1 , if  s t r [ i ] > s t r [ j ] 0 , if  s t r [ i ] < s t r [ j ] d p ( i + 1 , j − 1 ) , if  s t r [ i ] = s t r [ j ] dp_{(i,j)} = \begin{cases} 1, & \text{if } str[i] > str[j] \\ 0, & \text{if } str[i]<str[j] \\ dp_{(i+1,j-1)}, &\text{if } str[i]=str[j] \end{cases} dp(i,j)= 1,0,dp(i+1,j1),if str[i]>str[j]if str[i]<str[j]if str[i]=str[j]

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define For for(int i=1;i<=n;i++)
#define rFor for(int i=n;i>0;i--)
#define rep(i,sta,end) for(int i=sta;i<=end;i++)
#define rrep(i,end,sta) for(int i=end;i>=sta;i--)
#define ALL(x) for(auto item:x)
#define int long long
//#pragma GCC optimize(3,"Ofast","inline")inline void solve() {string str;cin >> str;int n = 1LL*str.size();vector<vector<int> > arr;rep(i,0,n){vector<int> tmp;rep(j,0,n){tmp.emplace_back(0);}arr.emplace_back(tmp);}rep(i,0,n-2){arr[i][i+1]=(str[i]>str[i+1]);}rep(len,3,n){rep(i,0,n-len){int j=i+len-1;if(str[i]==str[j]){arr[i][j]=arr[i+1][j-1];}else arr[i][j]=(str[i]>str[j]);}}int cot=0;rep(i,0,n-1){rep(j,i+1,n-1){cot+=arr[i][j];}}cout << cot << endl;
}
int32_t main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int num = 1LL;//cin>>num;while (num--){solve();//cout<<"已经执行solve函数"<<endl;}return 0LL;
}

http://www.ppmy.cn/embedded/2291.html

相关文章

全志R128 SDK HAL 模块开发指南之 UART

UART Universal Asynchronous Receiver/Transmitter&#xff0c;通用异步收发传输器 Compatible with industry-standard 16450/16550 UARTs64-Byte Transmit and receive data FIFOsSupports DMA controller interfaceSupports Software/ Hardware Flow ControlSupports IrD…

简单3步,OpenHarmony上跑起ArkUI分布式小游戏

标准系统新增支持了方舟开发框架&#xff08;ArkUI&#xff09;、分布式组网和 FA 跨设备迁移能力等新特性&#xff0c;因此我们结合了这三种特性使用 ets 开发了一款如下动图所示传炸弹应用。 打开应用在通过邀请用户进行设备认证后&#xff0c;用户须根据提示完成相应操作&am…

Linux安装docker(含Centos系统和Ubuntu系统)

一、Centos系统 1. 卸载旧版本依赖 sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine 2. 设置仓库 安装所需的软件包。yum-utils 提供了 yum-config-manager &…

如何在jmeter中把响应中的数据提取出来并引用

jmeter做接口测试过程中&#xff0c;经常遇到请求需要用到token的时候&#xff0c;我们可以把返回token的接口用后置处理器提取出来&#xff0c;但是在这种情况下&#xff0c;只能适用于当前的线程组&#xff0c;其他线程组无法引用到提取的token变量值&#xff0c;所以必须要生…

C++类和动态内存分配

类的动态内存分配和释放 C能够在程序运行时决定内存的分配&#xff0c;而不是只在编译阶段&#xff0c;因此&#xff0c;就可以根据程序的需要&#xff0c;而不是根据一系列严格的存储类型规则来使用内存&#xff0c;C使用new和delete运算符来动态控制内存&#xff0c;但是&am…

计算机网络——40各个层次的安全性

各个层次的安全性 安全电子邮件 Alice需要发送机密的报文m给Bob Alice 产生随机的对称秘钥&#xff0c; K s K_s Ks​使用 K s K_s Ks​对报文进行加密&#xff08;为了效率&#xff09;对 K s K_s Ks​使用Bob的公钥进行加密发送 K s ( m ) K_s(m) Ks​(m)和 K B ( K S ) K…

docker:chown socket at step GROUP: No such process

docker:chown socket at step GROUP: No such process 原因&#xff1a;docker无法找到Group组信息&#xff0c;docker组有可能被误删除&#xff0c; 解决方式&#xff1a; groupadd docker Docker是一种相对使用较简单的容器&#xff0c;我们可以通过以下几种方式获取信息&am…

近屿智能全新推出AI培训产品:AIGC大模型工程师与产品经理学习路径图

如今&#xff0c;人工智能和自然语言处理技术的发展&#xff0c;使得AI生成的内容&#xff08;AIGC&#xff0c;AI Generated Content&#xff09;领域开发出了巨大的潜力。就像业内巨头OpenAI公司&#xff0c;开发出了一系列自然语言处理模型ChatGPT&#xff0c;不仅带动了全世…

Jmeter接口自动化测试框架

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 关注公众号&#xff1a;互联网杂货铺&#xff0c;回复1 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 接口测试可以分为两部分&#xff1a; 一是线上接口&…

React-入门介绍

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;React篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来React篇专栏内容:React-入门介绍 目录 一、概述 1、介绍 2、开发工具的安装 3、React初识 二、JSX语法 1、…

初识微服务:重塑软件开发的未来

引言 随着信息技术的飞速发展&#xff0c;软件系统的复杂性和规模不断攀升&#xff0c;传统的单体应用架构已经难以满足现代业务的灵活性和可扩展性需求。在这样的背景下&#xff0c;微服务架构应运而生&#xff0c;成为当前软件开发领域的一大热门话题。本文将深入探讨微服务架…

ios ipa包上传需要什么工具

​ 目录 前言 一、IPA包的原理 二、IPA包上传的步骤 2.apk软件制作工具创建应用程序 3.构建应用程序 4.生成证书和配置文件 5.打包IPA包 6.上传IPA包 三、总结 前言 iOS IPA包是iOS应用程序的安装包&#xff0c;可以通过iTunes或者其他第三方应用商店安装到iOS设备上。…

java扩展jmeter依赖

前置条件 创建一个maven项目&#xff0c; 引入依赖 <dependency><groupId>org.apache.jmeter</groupId><artifactId>ApacheJMeter_core</artifactId><version>3.2</version> </dependency> <dependency><groupId&g…

在k8s集群中部署EdgeMesh

1. 前置准备 1.1 移除k8s master节点污点 如果k8s master节点上没有部署需要被代理的应用&#xff0c;也可以不执行此步骤&#xff1a; kubectl taint nodes --all node-role.kubernetes.io/master- 1.2 给 Kubernetes API 服务添加过滤标签 正常情况下你不会希望 EdgeMes…

ppt技巧:如何将Word文档大纲中导入到幻灯片中?

在PowerPoint中&#xff0c;将Word文档的大纲导入到新的幻灯片是一种非常实用的技巧。以下是详细的步骤&#xff1a; 首先&#xff0c;需要打开PowerPoint软件并打开原始的幻灯片文件。 在PowerPoint的顶部【开始】菜单栏中&#xff0c;找到并点击“新建幻灯片”按钮&#xff0…

【InternLM 实战营第二期作业04】XTuner微调LLM:1.8B、多模态、Agent

基础作业 训练自己的小助手认知 1.环境安装 安装XTuner 源码 # 如果你是在 InternStudio 平台&#xff0c;则从本地 clone 一个已有 pytorch 的环境&#xff1a; # pytorch 2.0.1 py3.10_cuda11.7_cudnn8.5.0_0studio-conda xtuner0.1.17 # 如果你是在其他平台&#x…

SpringBoot中全局异常捕获与参数校验的优雅实现

一&#xff0c;为什么要用全局异常处理&#xff1f; 在日常开发中&#xff0c;为了不抛出异常堆栈信息给前端页面&#xff0c;每次编写Controller层代码都要尽可能的catch住所有service层、dao层等异常&#xff0c;代码耦合性较高&#xff0c;且不美观&#xff0c;不利于后期维…

Springboot配置文件(application.yml)的加载顺序

spring boot 启动会扫描一下位置的application.properties或者application.yml文件作为Spring boot的默认配置文件 file…/config/ file…/ classpath:/config classpath:/ 以上是按照优先级从高到低的顺序&#xff0c;所有位置的文件都会被加载&#xff0c;高优先级配置内容会…

Java安全(应付面试)

一窍不通&#xff0c;应付面试&#xff0c;问的频繁 Fastjson https://blog.csdn.net/m0_46363249/article/details/122260021 ​ Fastjson可以将对象转换成Json字符串&#xff0c;XMLDecoder 可以将XML字符串还原成字符串&#xff0c;所以也是序列化和反序列化 与原生的java…

整理Meta GDC 2024 上关于XR、空间计算相关的分享

Meta 在 GDC 2024 上的全面覆盖,涵盖了如何利用 Meta Quest 构建全息游戏以及如何利用平台为开发者创造成功的会议。 视频分为 11 个部分,每个部分都是一场独特的会议,涵盖了从构建下一代 XR 体验到如何利用 Meta Quest 建立业务等话题 比如: 1、利用 Meta Quest 构建全息…