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

ops/2024/9/19 0:53:58/ 标签: 蓝桥杯, 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/ops/2796.html

相关文章

最新IntelliJ IDEA 2024.1 安装和快速配置教程

IntelliJ IDEA 2024.1 最新版如何快速入门体验?IntelliJ IDEA 2024.1 安装和配置教程 图文解说版 文章目录 IntelliJ IDEA 2024.1 最新版如何快速入门体验?IntelliJ IDEA 2024.1 安装和配置教程 图文解说版前言 第一步&#xff1a; IntelliJ IDEA 2024.1安装教程第 0 步&…

将Linux命令存为shell脚本

要将给定的命令保存为一个 shell 脚本文件&#xff0c;你可以按照以下步骤进行操作&#xff1a; 打开一个文本编辑器&#xff0c;比如 nano 或 vim。将以下命令粘贴到文本编辑器中&#xff1a; #!/bin/bashfind . -type f -name "*.xlsx" -exec tar -cvf xlsx_file…

吴恩达llama课程笔记:第四课提示词技术

羊驼Llama是当前最流行的开源大模型&#xff0c;其卓越的性能和广泛的应用领域使其成为业界瞩目的焦点。作为一款由Meta AI发布的开放且高效的大型基础语言模型&#xff0c;Llama拥有7B、13B和70B&#xff08;700亿&#xff09;三种版本&#xff0c;满足不同场景和需求。 吴恩…

【DL水记】循环神经网络RNN的前世今生,Transformer的崛起,Mamba模型

文章目录 RNN网络简介传统RNN网络结构RNN的分类 长-短期记忆网络 (LSTM)GRU网络横空出世的Transformer网络Self-AttentionVisionTransformer Mamba模型Reference: RNN网络简介 “当人类接触新事物时&#xff0c;他们不会从头开始思考。就像你在阅读这篇文章时&#xff0c;你会根…

Tomcat部署在linux服务器

一、下载软件包 tomcat:https://mirrors.tuna.tsinghua.edu.cn/apache/tomcat/tomcat-9/v9.0.31/bin/apache-tomcat-9.0.31.zip jdk:https://www.oracle.com/java/technologies/javase-downloads.html 如何想使用tomcat9的话,官方要求JRE的版本必须是8以上的,所以在安装…

[通俗易懂:Linux标准输入/输出和重定向]Shell脚本之 > /dev/null 2>1命令详解

目录标题 一、> /dev/null 2>&1 命令解析二、/dev/null 文件浅显理解三、标准输入、标准输出、标准错误输出四、输入重定向、输出重定向五、命令作用与应用场景 如果想看命令意义&#xff0c;可以直接跳到第五部分 一、> /dev/null 2>&1 命令解析 我们在别…

机器学习基础

机器学习基础 引言 在探索智能算法和数据科学的广阔海洋中&#xff0c;机器学习犹如一座连接着理论与实际应用的桥梁。你或许已经听说过机器学习在现代科技中的无处不在&#xff0c;从推荐系统到自动化驾驶&#xff0c;它正悄然改变我们的世界。但在这些复杂系统的核心&#x…

QML学习之加载gif

在QML中直接加载GIF图片是不支持的&#xff0c;因为QML的Image元素不支持动画GIF。不过&#xff0c;你可以使用AnimatedImage元素来播放GIF。AnimatedImage是Qt QML模块的一部分&#xff0c;可以加载和播放GIF动画。 import QtQuick 2.0 import QtQuick.Controls 2.0 import Qt…

Mac使用Idea新手常用快捷键

Mac使用Idea新手常用快捷键 前言常用指令1、选中多个文件&#xff0c;不连续2、点进去查看某个类的代码3、复制某个类的全类名4、鼠标滚轮选中多行&#xff0c;然后选中这些行上同一列光标所在的单词 前言 入职新公司后用的是mac&#xff0c;从windows切换到mac&#xff0c;一…

Rust面试宝典第2题:逆序输出整数

题目 写一个方法&#xff0c;将一个整数逆序打印输出到控制台。注意&#xff1a;当输入的数字含有结尾的0时&#xff0c;输出不应带有前导的0。比如&#xff1a;123的逆序输出为321&#xff0c;8600的逆序输出为68&#xff0c;-609的逆序输出为-906。 解析 这道题本身并没有什么…

2024深圳国际机器人展览会

时 间&#xff1a;2024年11月13-17日 地 点&#xff1a;深圳会展中心 ◆展会背景Exhibition background&#xff1a; 机器人被誉为“制造业皇冠顶端的明珠”&#xff0c;其研发、制造、应用…

【C语言笔记】sprintf和snprintf的区别

一&#xff0c;简介 sprintf() 和 snprintf() 都是用于格式化输出到字符串中的函数&#xff0c;但它们有一些重要的区别&#xff1a; 二&#xff0c;相同点&#xff1a; 功能&#xff1a; 两者都用于将格式化的字符串输出到一个目标字符串中。这些函数的用法类似于 printf()…

姿态估计-人脸识别mesh-3d手势识别-3d目标检测-背景分割-人脸关键点

往期热门博客项目回顾&#xff1a;点击前往 计算机视觉项目大集合 改进的yolo目标检测-测距测速 路径规划算法 图像去雨去雾目标检测测距项目 交通标志识别项目 yolo系列-重磅yolov9界面-最新的yolo 姿态识别-3d姿态识别 深度学习小白学习路线 AI健身教练-引体向上…

Python数据容器(三)

一.tuple&#xff08;元组&#xff09; 1.元组同列表一样&#xff0c;都可以封装多个、不同类型的元素在内。 但最大的不同点在于&#xff1a;元组一旦定义完成&#xff0c;就不可修改。 2.元组定义&#xff1a;定义元组使用小括号&#xff0c;且使用逗号隔开各个数据&#…

LeetCode 2007. 从双倍数组中还原原数组

题目链接 https://leetcode.cn/problems/find-original-array-from-doubled-array/description/?envTypedaily-question&envId2024-04-18 先给数组排序&#xff0c;然后使用hashmap来标记元素是双倍之前还是之后的 class Solution {public int[] findOriginalArray(int[…

微信小程序日期增加时间完成订单失效倒计时(有效果图)

效果图 .wxml <view class"TimeSeond">{{second}}</view>.js Page({data: {tiem_one:,second:,//倒计时deadline:,},onLoad(){this.countdown();},countdown(){let timestamp Date.parse(new Date()) / 1000;//当前时间戳let time this.addtime(2024…

Flink学习(六)-容错处理

前言 Flink 是通过状态快照实现容错处理 一、State Backends 由 Flink 管理的 keyed state 是一种分片的键/值存储&#xff0c;每个 keyed state 的工作副本都保存在负责该键的 taskmanager 本地中。 一种基于 RocksDB 内嵌 key/value 存储将其工作状态保存在磁盘上&#x…

基于simulink的配网自动化仿真

1. powergui的概念 在Simulink的PowerGUI中&#xff0c;将discrete的时间参数设置为1e-5秒&#xff08;即0.00001秒或10微秒&#xff09;&#xff0c;通常表示模型中的离散事件或控制逻辑将以这个时间间隔进行更新或执行。 2.在电力系统中&#xff0c;通常所说的10kV&#xf…

【VSLAM】VINO-Mono安装部署与运行

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍VINO-Mono安装部署与运行。 学其所用&#xff0c;用其所学。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下次更新不迷…

在Mac中打开终端的3种方法

在使用Mac时&#xff0c;有时需要深入研究设置&#xff0c;或者完成一些开发人员级的命令行任务。为此&#xff0c;你需要终端应用程序来访问macOS上的命令行。下面是如何启动它。 如何使用聚焦搜索打开终端 也许打开终端最简单、最快的方法是通过聚焦搜索。要启动聚焦搜索&a…