题意:给定一01序列和两种操作:1.将单个字符翻转 2.将前x个字符翻转。问将序列全部变为0至少需要多少次操作 。
思路:分别考虑将前i个字符全部变为1和全部变为0的最少操作次数dp[i][0]dp[i][1],则状态转移方程如下:

if (a[i]) {
      dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
      dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1);
    } else {
      dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1);
      dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
}

似乎可以简化,不过这样也好理解。

当前位为1:
全变成0的次数:前i-1位的操作次数+1
全变成1的次数:前i-1位已经全1的话,只要将第二种操作反转的字符多一个,不需要增加操作次数,前i-1位全为0的话就多一次操作,二者取min
当前位为0:
和上面说的恰好相反
AC代码:

#include <bits/stdc++.h>
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 100005
using namespace std;
int T = 1;
int a[N], dp[N][2];

int main() {
    //cin>>T;
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        dp[0][0] = a[0];
        dp[0][1] = 1 - a[0];
        for (int i = 1; i < n; i++) {
            if (a[i]) {
                dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
                dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1);
            } else {
                dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1);
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
            }
        }
        cout << min(dp[n - 1][0], dp[n - 1][1]+1) << endl;
    }
}