分数: 600 点
问题陈述
给你一个字符串 S = s_1 s_2 \ldots s_N 长度 N 组成 0的和 1的。
求最大整数 K 这样有一个序列 K 整数对 \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) 满足以下所有三个条件。
- 1 \leq L_i \leq R_i \leq N 对于每个 i = 1, 2, \ldots, K.
- R_i \lt L_{i+1} 为 i = 1, 2, \ldots, K-1.
- 字符串 s_{L_i}s_{L_i+1} \ldots s_{R_i} is 严格按字典顺序较小 比字符串 s_{L_{i+1}}s_{L_{i+1}+1}\ldots s_{R_{i+1}}.
约束
- 1 \leq N \leq 2.5 \times 10^4
- N 是一个整数。
- S 是一个长度为的字符串 N 组成 0的和 1的。
输入
输入由标准输入按以下格式给出:
N S
输出
打印答案。
示例输入 1
7 0101010
示例输出 1
3
对于 K = 3,满足条件的一个序列是 (L_1, R_1) = (1, 1), (L_2, R_2) = (3, 5), (L_3, R_3) = (6, 7)。
确实, s_1 = 0 按字典顺序严格小于 s_3s_4s_5 = 010,和 s_3s_4s_5 = 010 按字典顺序严格小于 s_6s_7 = 10.
对于 K \geq 4,没有顺序 \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) 满足条件。
示例输入 2
30 000011001110101001011110001001
示例输出 2
9