牛客练习赛67 D. 牛妹爱数列

Description

他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：
1.单点修改：将位置x上的数翻转（0变1,1变0）；
2.前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。
他现在想要最小化翻转次数，使得数列上的所有数都变为0。

Solution

贪心贪不动，考虑dp，主要在于如何表示状态,设：

$dp[i][0]$ 表示到了第i个位置，把前面的都变成0的最小操作数

$dp[i][1]$ 表示到了第i个位置，把前面的都变成1的最小操作数

那么很容易就能表示出状态转移方程，最后输出 $min(dp[n][0], dp[n][1] + 1)$ 即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int a[N], dp[N][2];
int main() {
    int n; cin >> n;
    memset(dp, 13, sizeof(dp));
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(a[1]) dp[1][1] = 0, dp[1][0] = 1;
    else dp[1][1] = 1, dp[1][0] = 0;
    for(int i = 2; i <= n; i++) {
        if(a[i]) {
            dp[i][0] = min(dp[i - 1][1] + 1, dp[i - 1][0] + 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] + 1, dp[i - 1][1] + 1);
        }
    }
    cout << min(dp[n][0], dp[n][1] + 1) << "\n";
  return 0;
}