题解 | #游游的01串操作#

题意

这里有一个由0或1构成字符串，我们需要通过变换字符（1或0）使字符串中相邻的两个字符互不相等。又知道更改第位的字符需花费，求使字符串合法的最小花费？

思路

因为我们我那时要求最小花费，但是此处要考虑两个值。

• 改变字符的操作数量
• 改变每一个字符的花费不同

这时我们通过最小值又不可以直接贪心便可以想到动态规划，这道题变简单了！

状态：表示到了第个字符，当前字母的状态（1/0）。

转移：若当前这个字符状态为1：

• 当前位置不变 dp[i][1] = dp[i - 1][0];直接等于上一个字符为0的情况。
• 把当前位置的字符变成0dp[i][0] = dp[i - 1][1] + i + 1;（枚举字符串的每一位从0开始）等于上一个字符为0的情况再加上所需的花费。

总代码

#include<bits/stdc++.h>
#define int long long//防止爆int, 本题不用。

using namespace std;

const int MAXX = 1e6 + 5;

string s;
int dp[MAXX][2];


signed main(){
    cin >> s;
    for(int i = 0; i <= s.size(); i++){
        dp[i][0] = dp[i][1] = LLONG_MAX;
    }
    if(s[0] == '1'){
        dp[0][1] = 0;
        dp[0][0] = 1;
    }else{
        dp[0][0] = 0;
        dp[0][1] = 1;
    }
    for(int i = 1; i < s.size(); i++){
        if(s[i] == '1'){
            dp[i][0] = dp[i - 1][1] + i + 1;
            dp[i][1] = dp[i - 1][0];
        }else{
            dp[i][1] = dp[i - 1][0] + i + 1;
            dp[i][0] = dp[i - 1][1];
        }
    }
    cout << min(dp[s.size() - 1][0], dp[s.size() - 1][1]);
    
    return 0;
}