牛妹爱数列_牛客博客

题目

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

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

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

解题思路

动态规划

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

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

遍历序列，如果 $a[i]=1$ ，

要想将序列前 $i$ 个数变为 0，可以使用单点修改直接将 $a[i]$ 变为 0，翻转次数为 $dp[i-1][0]+1$ 。
或者使用前缀修改，翻转次数为 $dp[i-1][1]+1$ 。
所以， $dp[i][0] = \min(dp[i-1][0]+1, dp[i-1][1]+1)$ 。
要想将序列前 $i$ 个数变为 1，可以不需更改，翻转次数为 $dp[i-1][1]$ 。
或者使用单点修改，翻转次数为 $dp[i-1][0]+1$ 。
所以， $dp[i][1] = \min(dp[i-1][1],dp[i-1][0]+1)$ 。

同理，如果 $a[i]=0$ ，

$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)$

根据上述的状态转移方程可以看出，当前的状态只与前一个状态有关。
所以，可以对上面的 DP 进行空间上的优化，使空间复杂度从 $O(n)$ 降为 $O(1)$ ，只需使用 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;
}