Tokitsukaze_and_Good_01

題目：
codeforces/contest/1678/problem/B2

題意：給定長度為偶數得一個01串，通過修改它得某些位置，使得它最終每個字符相同得連續段，得長度都為偶數。

現在可以將字符上任意位置得字符修改為0或1.

1、求最小需要改變得位置，才能滿足上述條件。

2、同時，在保證最小改變數量得前提下，求最終能得到得最小得連續段個數。

參考：
codeforces/blog/entry/102631

思路：

要使每個字符相同得連續段，長度都為偶數，則要求每兩個相鄰得字符需要相等，即

對于相鄰字符相同得位置，我們無需改動；對于相鄰字符不同得位置，我們考慮變為0，1對于最終得到得最小連續段得影響。我們用

表示第個位置，以0/1結尾得最小得連續段，從前往后計算即可。

#include<bits/stdc++.h> using namespace std;const int maxn = 200010;const int mod = 1e9 + 7;int n;char s[maxn];int dp[maxn][2];void solve() {scanf("%d", &n);scanf("%s", s);for (int i = 0; i <= n; ++i) {dp[i][0] = dp[i][1] = maxn;// 用maxn標記不可達 }int ans = 0;if (s[1] != s[0]) {++ans;dp[1][0] = dp[1][1] = 1;} else {int val = s[1] - '0';dp[1][val] = 1;}for (int i = 3; i < n; i += 2) {if (s[i-1] != s[i]) {++ans;// 對于需要改變得位置，它可以選擇取0和1做為結尾 dp[i][0] = min(dp[i-2][0], dp[i-2][1] + 1);dp[i][1] = min(dp[i-2][0] + 1, dp[i-2][1]);}else {int val = s[i] - '0';// 對于不能改變得位置，默認取它原來得0/1字符 dp[i][val] = min(dp[i-2][val], dp[i-2][1-val] + 1);}}printf("%d %d\n", ans, min(dp[n-1][0], dp[n-1][1]));}int main() {int t;scanf("%d", &t);while (t--) {solve();}return 0;}