[USACO12NOV] Clumsy Cows S

题意

给定一个括号串，每次可以把一个 ( 翻成 ) 或把一个 ) 翻成 (。

要求最少翻转多少次，才能让字符串变成合法括号串。

思路

先看最直接的办法：枚举哪些位置翻转，然后检查括号串是否平衡。

这个做法最容易理解：

cpp

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
37
38#include <bits/stdc++.h>
using namespace std;

string s;

bool ok(const string& t) {
    int balance = 0;
    for (char c : t) {
        if (c == '(') balance++;
        else balance--;
        if (balance < 0) return false;
    }
    return balance == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;

    int n = s.size();
    int ans = n;
    for (int mask = 0; mask < (1 << n); mask++) {
        string t = s;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                cnt++;
                t[i] = (t[i] == '(' ? ')' : '(');
            }
        }
        if (ok(t)) ans = min(ans, cnt);
    }

    cout << ans << '\n';
    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它按位置依次决定当前括号翻或不翻，递归生成完整选择后，叶子节点统一检查括号串是否合法，并统计最少翻转次数：

另一种暴力写法：01 序列

cpp

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65// brute_01_style.cpp：01 序列风格暴力，按位置依次决定这个括号翻或不翻。
#include <bits/stdc++.h>
using namespace std;

string s, current_string;
int n;
int flip_pos[105]; // flip_pos[i] = 0/1，表示第 i 个位置不翻/翻
int answer;

bool is_valid() {
    int balance = 0;
    for (int i = 0; i < n; i++) {
        char ch = s[i];
        if (flip_pos[i] == 1) {
            ch = (ch == '(' ? ')' : '(');
        }
        if (ch == '(') {
            balance++;
        } else {
            balance--;
        }
        if (balance < 0) {
            return false;
        }
    }
    return balance == 0;
}

int calc_answer() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (flip_pos[i] == 1) cnt++;
    }
    return cnt;
}

void dfs_flip(int dep) {
    if (dep == n) {
        if (is_valid()) {
            int value = calc_answer();
            if (answer > value) answer = value;
        }
        return;
    }

    // 第 dep 个位置的 01 选择：0 不翻，1 翻。
    for (int i = 0; i <= 1; i++) {
        flip_pos[dep] = i;
        dfs_flip(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    n = (int)s.size();

    answer = n + 1;
    dfs_flip(0);

    cout << answer << '\n';
    return 0;
}

但显然不能直接用来做正解。

这题的关键在于前缀性质。

扫描字符串时维护 balance = 左括号数 - 右括号数：

遇到 (，balance++
遇到 )，balance--

如果某一步 balance < 0，说明当前前缀里右括号太多了，后面再怎么补都救不回这个前缀，所以必须立刻把当前这个 ) 翻成 (。

翻完以后，当前前缀就从 -1 变成了 1，因此：

ans++
balance = 1

扫描结束后，如果 balance > 0，说明还有多余的左括号。每两个左括号可以通过一次翻转变成一对合法括号，所以还要再加上 balance / 2。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

string s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;

    int ans = 0;
    int balance = 0;

    for (char c : s) {
        if (c == '(') {
            balance++;
        } else {
            balance--;
        }

        if (balance < 0) {
            ans++;
            balance = 1;
        }
    }

    ans += balance / 2;
    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(1)$

总结

这题的核心不是枚举翻转位置，而是利用前缀合法性做贪心。

一旦前缀失衡，就必须立即修正当前右括号；剩下的多余左括号再统一成对处理即可。

[USACO12NOV] Clumsy Cows S

目录

题意

思路

代码

复杂度

总结