CF2103B Binery Typewriter

一定会按下 $n$ 次键来打出 $n$ 个字符，所以减少操作步数的唯一路径是减少移动的步数，也就是让 0 和 1 尽量地连续。

注意到，只进行 $1$ 次反转操作最多只可能让移动的步数减少 $2$。故而，若整个序列 0 和 1 已经足够连续（即最多只有 $2$ 段分开的序列），则没有必要进行反转，否则进行反转。若只有原本 $2$ 移动的操作，则总操作步数最多减 $1$，否则最多减 $2$。

注意到，一开始是从打 0 的位置开始移动的，所以可以先将原本的序列的前端加上一个 0 后再对改进后的序列进行上述计算，最后再减 $1$ 即可。

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
int main()
{
    int T;
    cin>>T;
    while (T)
    {
        int n;
        string s,str;
        cin>>n>>s;
        str="0"+s;
        int cnt=0;
        long long ans=n;
        for (int i=0;i<n;i++)
        {
            if (str[i]!=str[i+1])
            {
                cnt++;
            }
        }
        if (cnt==0||cnt==1)
        {
            ans+=cnt;
        }
        else if (cnt==2)
        {
            ans+=cnt-1;
        }
        else
        {
            ans+=cnt-2;
        }
        printf("%lld\n",ans);
        T--;
    }
    return 0;
}