牛妹爱数列

题目

有一个长度为 n 的序列 a，保证它是一个 01 序列，并执行以下两种操作：

1. 单点修改：将位置 x 上的数翻转（0 变 1，1 变 0）；
2. 前缀修改：将位置 1~x 上的数翻转（每个数都 0 变 1，1 变 0）。

求：使得数列上的所有数都变为 0 的最小翻转次数。

解题思路

动态规划

表示将序列中前 个数都变为 0 的最小翻转次数。

表示将序列中前 个数都变为 1 的最小翻转次数。

遍历序列，如果 ，

• 要想将序列前 个数变为 0，可以使用单点修改直接将 变为 0，翻转次数为 。
  或者使用前缀修改，翻转次数为 。
  所以，。
• 要想将序列前 个数变为 1，可以不需更改，翻转次数为 。
  或者使用单点修改，翻转次数为 。
  所以，。

同理，如果 ，

根据上述的状态转移方程可以看出，当前的状态只与前一个状态有关。
所以，可以对上面的 DP 进行空间上的优化，使空间复杂度从 降为 ，只需使用 2 个变量实时更新前一个状态。

C++代码

#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int a;
    int pre[2] = {0};
    int cur[2] = {0};
    for(int i=1; i<=n; ++i){
        cin >> a;
        if(a==1){
            cur[0] = min(pre[0]+1, pre[1]+1);
            cur[1] = min(pre[0]+1, pre[1]);
        }
        else{
            cur[0] = min(pre[0], pre[1]+1);
            cur[1] = min(pre[0]+1, pre[1]+1);
        }
        pre[0] = cur[0];
        pre[1] = cur[1];
    }
    cout << cur[0] << endl;
    return 0;
}