上海计算机学会 2023年12月月赛 丙组T5 特定的串（动态规划）

第五题：T5特定的串

标签：动态规划
题意：给定$01$串，可以修改其中任意一个字符，把$0$变成$1$，把$1$变成$0$，不能删除或者增加$01$字符，求最少修改个数，使得给定序列中不含特定子串$110$。
题解：
贪心 $90$ 分解法：比较容易想到的一个思路是把$11$变成$10$，或者把所有$0$变成 $1$。
这个思路有以下几个反例：
$101111101$（这个只需要把后面的那个$0$改成$1$）
$1100111101$（这个可以把第$2$个$1$改成 $0$，最后那个$0$改成$1$）
像第二个反例，我们需要思考把两种贪心策略进行结合。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, num = 0; // num: 连续1的个数
    // c1: 11110变成10100
    // c2: 11011变成11111
    int c1 = 0, c2 = 0;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            c2++;
            c1 += num / 2;
            num = 0;
        } else {
            num++;
        }
    }
    cout << min(c1, c2) << endl;
    return 0;
}
// 9
// 101111101

// 10
// 1100111101
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

动态规划解法：
$dp[i][0/1][0/1]$：以第$i$位为结尾，使得前$i$个字符中不包含$110$，且第$i$位是$0$或$1$，第$i-1$位是$0$或$1$的最少修改个数。
考虑状态转移：
一、如果$s[i]$修改成$0$

1. $dp[i][0][0]$（$s[i]=0,s[i-1]=0$）可以从$s[i-2]=0/1$转移过来，即$dp[i][0][0]=min(dp[i-1][0][0],dp[i-1][0][1])$
2. $dp[i][0][1]$（$s[i]=0,s[i-1]=1$）只能从$s[i-2]=0$转移过来，即$dp[i][0][0]=dp[i-1][1][0]$

二、如果$s[i]$修改成$1$
那不管是$001$、$101$、$111$$011$都是可以的。所以
$dp[i][1][0]=min(dp[i-1][0][0],dp[i-1][0][1])$
$dp[i][1][1]=min(dp[i-1][1][0],dp[i-1][1][1])$
然后再上面转移的过程中要考虑$s[i]$是否修改，所以要把这个修改的代价都带上。
最后从$dp[n-1]$的四种情况里面取最小值就可以了。
代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 +10;
char s[N];
int dp[N][2][2];
// 以第i位为结尾，使得前i个字符中不包含110，
// 且第i位是0或1，第i-1位是0或1的最少修改个数

int main() {
    int n;
    cin >> n >> s;
    int s0 = s[0] - '0', s1 = s[1] - '0';
    dp[1][s1][s0] = 0;
    dp[1][s1^1][s0] = dp[1][s1][s0^1] = 1;
    dp[1][s1^1][s0^1] = 2;

    for (int i = 2; i < n; i++) {
        int d = 0;
        // s[i]修改成0
        if (s[i] != '0') d = 1;
        dp[i][0][0] = min(dp[i-1][0][0], dp[i-1][0][1]) + d;
        dp[i][0][1] = dp[i-1][1][0] + d;

        // s[i]修改成1
        d = 0;
        if (s[i] != '1') d = 1;
        dp[i][1][0] = min(dp[i-1][0][0], dp[i-1][0][1]) + d;
        dp[i][1][1] = min(dp[i-1][1][0], dp[i-1][1][1]) + d;
    }
    cout << min(min(dp[n-1][0][0], dp[n-1][0][1]), min(dp[n-1][1][0], dp[n-1][1][1]));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33