P12143 [蓝桥杯 2025 省 A] 好串的数目

对于一个长度为 $n$ 的字符串 $s = s_0s_1 \cdots s_{n-1}$ 来说，子串的定义是从中选出两个下标 $l, r$ $(0 \leq l \leq r \leq n-1)$，这之间所有的字符组合起来的一个新的字符串：$s' = s_ls_{l+1} \cdots s_r$ 就是其中一个子串。 现在给出一个只有数字字符 $0 \sim 9$ 组成的数字字符串，小蓝想要知道在其所有的子串中，有多少个子串是好串。一个子串是好串，当且仅当它满足以下两个条件之一： 1. 单字符子串一定是好串，即当子串长度为 $1$ 时，它总是好串； 2. 长度大于 $1$ 时，可以拆分为两个**连续非递减子串**： 一个串 $p = p_0p_1 \cdots p_{k-1}$ 为**连续非递减子串**是指，对于所有 $1 \leq i < k$，满足 $p_i = p_{i-1}$ 或 $p_i = p_{i-1} + 1$。即数字串中的每一个数字，要么等于上一个数字，要么等于上一个数字加 $1$。例如 `12233`、`456` 是连续非递减子串。

输入一行包含一个字符串 $s$。

输出一行包含一个整数表示答案，即好串的数目。

### 样例说明 1 - 长度为 $1$ 的好串：`1`、`2`、`2`、`5`、`8`，共 $5$ 个； - 长度为 $2$ 的好串：`12`、`22`、`25`、`58`，共 $4$ 个； - 长度为 $3$ 的好串：`122`、`225`，共 $2$ 个； - 长度为 $4$ 的好串：`1225`，共 $1$ 个； 总计 $5 + 4 + 2 + 1 = 12$ 个。 ### 样例说明 2 - 长度为 $1$ 的好串：`9`、`7`、`8`、`5`、`6`，共 $5$ 个； - 长度为 $2$ 的好串：`97`、`78`、`85`、`56`，共 $4$ 个； - 长度为 $3$ 的好串：`978`、`785`、`856`，共 $3$ 个； - 长度为 $4$ 的好串：`7856`，共 $1$ 个； 总计 $5 + 4 + 3 + 1 = 13$ 个。 ### 评测用例规模与约定 - 对于 $20\%$ 的评测用例，$1 \leq n \leq 5$； - 对于 $40\%$ 的评测用例，$1 \leq n \leq 20$； - 对于 $60\%$ 的评测用例，$1 \leq n \leq 100$； - 对于 $70\%$ 的评测用例，$1 \leq n \leq 10^3$； - 对于 $80\%$ 的评测用例，$1 \leq n \leq 10^4$； - 对于所有评测用例，$1 \leq n \leq 10^5$，$s$ 中只包含数字字符 $0 \sim 9$。