求01反转次数

题目描述

Yuilice最近给学生们上了一节动态规划的课程，为了让各位同学了解到动态规划的核心内容是划分阶段与建立状态转移方程，于是他出了这一道题。

Yuilice会给各位同学一个字符串$S$，这个字符串$S$只会由字符$0$与字符$1$组成，Yuilice可以对这个字符串进行一些操作，操作的内容如下。

• Yuilice可以选中下标为$i(1 \leq i \leq S.length)$的字符，将位于下标$i$后的所有字符$i \leq j \leq S.length$全部变为相反的数，例如0全部变成1，1全部变成0。

现在，Yuilice想知道，他最少需要几次操作，才可以将字符串$S$变为不递减的字符串？

输入格式

第一行输入一个正整数$t(1 \leq t \leq 10^4)$，代表接下来有$t$组样例测试。

随后$t$行，每行给出一个数字$n(1 \leq n \leq 10^5)$，代表字符串$S$的长度。

输出格式

每一组样例，输出一个整数代表其最少操作次数

样例 #1

样例输入 #1

5
1
1
3
101
5
10101
10
1010101010
7
0001000

样例输出 #1

0
2
4
9
1

提示

NOTE

第一组样例当中，字符串本身便不是递减的。

第二组样例当中，我们需要在$i = 2$的时候转变字符串后两个字符变为$10$，于$i = 3$的时候转变后一个字符为$1$，最后将字符串变为$111$则可完成。

$My$ $idea:$

• 正状态，在正状态下，所有字符都是原样的，比较也拿原本的数值比较，经过一次翻转变成反状态。

• 反状态，在反状态下，所有字符都是翻转过来的，0当1算，1当0算，拿反过来的数值进行比较，经过一次翻转变成正状态。

• 阶段 ：我们只需要枚举1~n每两个数值是否成非递减，比较的时候参考正反状态分割成两个阶段，按照正反状态的规则来比较，如果不成非递减顺序，那么我们就给他翻转1次，记录次数，最后输出即可。

• 状态转移方程：设F为正反状态的标记，F为true的时候代表是正，F为false代表是反。

$F = True$

• $S[i] <= S[i]+1 , DP[i+1] = DP[i];$
• $S[i] > S[i]+1 , DP[i+1] = DP[i] + 1;$

$F = False$

• $S[i] >= S[i]+1 , DP[i+1] = DP[i];$
• $S[i] < S[i]+1 , DP[i+1] = DP[i] + 1;$

最后输出$DP[S.length()]$即可。