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

string s;
int n, k;
ll ans = 1e18;
const int MAXN = 4005;

ll good[MAXN][MAXN];
ll dp[MAXN][MAXN];

ll naw(int i, int j) { return good[j][j] - good[i - 1][j] - good[j][i - 1] + good[i - 1][i - 1]; }

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> k >> s;

    for (int i = 1; i <= n; i++) {
        string substring;
        int bal = 0;
        for (int j = 1; j <= n; j++) {
            good[i][j] = -good[i - 1][j - 1] + good[i - 1][j] + good[i][j - 1];
            if (j >= i && bal >= 0) {
                bal += (s[j - 1] == '(' ? 1 : -1);
                if (bal == 0) good[i][j]++;
            }
        }
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = 1e18;
        }
    }

    dp[0][0] = 0;
    for (int pref = 1; pref <= n; pref++) {
        for (int blocks = 1; blocks <= k; blocks++) {
            // for (int last = blocks; last <= pref; last++) cerr << dp[last - 1][blocks - 1] << "
            // "; cerr << "\n"; for (int last = blocks; last <= pref; last++) cerr << naw(last,
            // pref) << " "; cerr << "\n";

            // for (int last = blocks; last <= pref; last++)
            //     cerr << dp[last - 1][blocks - 1] + naw(last, pref) << " ";
            // cerr << "\n\n";
            for (int last = blocks; last <= pref; last++) {
                dp[pref][blocks] =
                    min(dp[pref][blocks], dp[last - 1][blocks - 1] + naw(last, pref));
            }
        }
    }

    cout << dp[n][k] << "\n";
}

// 13.438s