#P19005. 【CodeChef START263A】Copycat

【CodeChef START263A】Copycat

题目描述

有一个长度为 NN 的二进制字符串 SS,字符从 11 到 NN 编号。每次操作可以选一个位置 ii(1≤i<N1 \le i < N),用右邻字符 Si+1S_{i+1} 覆盖当前位置的字符 SiS_i。其他位置保持原样。

最少需要操作多少次,才能使 SS 中的字符从左到右非降序排列?也就是说,最终所有的 00 都应位于所有的 11 之前。

输入格式

第一行是整数 TT,表示测试组数。

每组数据占两行。第一行是字符串长度 NN,第二行是字符串 SS。

输出格式

每组数据输出一行,包含一个整数,表示最少操作次数。

数据范围

  • 1≤T≤10001 \le T \le 1000。
  • 1≤N≤2001 \le N \le 200。
  • SS 的每个字符都是 00 或 11。

样例

4
3
110
5
01001
5
10101
9
011010011
2
1
2
3

CodeChef 原题:Copycat