Tokitsukaze_and_Good_01

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

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

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

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

2、同時(shí)，在保證最小改變數(shù)量得前提下，求最終能得到得最小得連續(xù)段個(gè)數(shù)。

參考：
codeforces/blog/entry/102631

思路：

要使每個(gè)字符相同得連續(xù)段，長度都為偶數(shù)，則要求每兩個(gè)相鄰得字符需要相等，即

對于相鄰字符相同得位置，我們無需改動(dòng)；對于相鄰字符不同得位置，我們考慮變?yōu)?，1對于最終得到得最小連續(xù)段得影響。我們用

表示第個(gè)位置，以0/1結(jié)尾得最小得連續(xù)段，從前往后計(jì)算即可。

#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標(biāo)記不可達(dá) }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做為結(jié)尾 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';// 對于不能改變得位置，默認(rèn)取它原來得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;}