2020年广东工业大学第十届文远知行杯新生程序设计竞赛（同步赛）A. 肥猪的钢琴床

发表于 分类于

链接

https://ac.nowcoder.com/acm/contest/9692/A

题意

将 $01$ 字符串转化为最多只有一段连续 $1$ 的字符串，求最小删除字符数。

思路

转化后的字符串可化为 $0\cdots0+1\cdots1+0\cdots0$ 三段，每一段的长度都可能为 $0$。

记 $dp[i][0/1/2]$ 为第 $i$ 个字符位于 $1/2/3$ 段需要删除的最小字符（第 $i$ 个字符可能要被删除）。

状态转移方程很简单。

代码

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
34
35
36
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=1e6+5;
char s[N];
int n,dp[N][3];
int main() {
    //freopen("E:/OneDrive/IO/in.txt","r",stdin);
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++) {
        if(s[i]=='1') {
            dp[i][0]=dp[i-1][0]+1;
            dp[i][1]=min(dp[i-1][0],dp[i-1][1]);
            dp[i][2]=min(dp[i-1][1],dp[i-1][2])+1;
        }
        else {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;
            dp[i][2]=min(dp[i-1][1],dp[i-1][2]);
        }
    }
    printf("%d\n",min({dp[n][0],dp[n][1],dp[n][2]}));
    return 0;
}