2070: [蓝桥杯2023初赛] 更小的数
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1135
通过：351
题目描述
小蓝有一个长度均为 n 且仅由数字字符 0 ~ 9 组成的字符串，下标从 0 到 n - 1。
你可以将其视作是一个具有 n 位的十进制数字 num。
小蓝可以从 num 中选出一段连续的子串并将子串进行反转，最多反转一次。
小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件numnew < num。
请你帮他计算下一共有多少种不同的子串选择方案。
只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。
注意，我们允许前导零的存在，即数字的最高位可以是 0 ，这是合法的。
输入格式
输入一行包含一个长度为 n 的字符串表示num（仅包含数字字符0 ~ 9），从左至右下标依次为0 ~ n - 1。
对于 20% 的评测用例，1 ≤ n ≤ 100 ；
对于 40% 的评测用例，1 ≤ n ≤ 1000 ；
对于 100% 评测用例，1 ≤ n ≤ 5000 。
对于 20% 的评测用例，1 ≤ n ≤ 100 ；
对于 40% 的评测用例，1 ≤ n ≤ 1000 ；
对于 100% 评测用例，1 ≤ n ≤ 5000 。
输出格式
输出一行包含一个整数表示答案。
输入样例 复制
210102输出样例 复制
8数据范围与提示
一共有 8 种不同的方案：
1）所选择的子串下标为0-1 ，反转后的numnew = 120102 < 210102 ；
2）所选择的子串下标为0-2 ，反转后的numnew = 012102 < 210102 ；
3）所选择的子串下标为0-3 ，反转后的numnew = 101202 < 210102 ；
4）所选择的子串下标为0-4 ，反转后的numnew = 010122 < 210102 ；
5）所选择的子串下标为0-5 ，反转后的numnew = 201012 < 210102 ；
6）所选择的子串下标为1-2 ，反转后的numnew = 201102 < 210102 ；
7）所选择的子串下标为1-4 ，反转后的numnew = 201012 < 210102 ；
8）所选择的子串下标为3-4 ，反转后的numnew = 210012 < 210102 。
1）所选择的子串下标为0-1 ，反转后的numnew = 120102 < 210102 ；
2）所选择的子串下标为0-2 ，反转后的numnew = 012102 < 210102 ；
3）所选择的子串下标为0-3 ，反转后的numnew = 101202 < 210102 ；
4）所选择的子串下标为0-4 ，反转后的numnew = 010122 < 210102 ；
5）所选择的子串下标为0-5 ，反转后的numnew = 201012 < 210102 ；
6）所选择的子串下标为1-2 ，反转后的numnew = 201102 < 210102 ；
7）所选择的子串下标为1-4 ，反转后的numnew = 201012 < 210102 ；
8）所选择的子串下标为3-4 ，反转后的numnew = 210012 < 210102 。