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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;

#define assert_range(x,a,b) assert((a) <= (x) and (x) <= (b))
using ll = long long;
const ll INF = 1e18;

int main() {
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    // pref_sum[i][j] := num good substrings in s[i..j] starting at i
    vector<vector<ll>> pref_sum(n, vector<ll>(n)); 

    // f[i][j] := num good substrings in s[i..j]
    vector<vector<ll>> f(n, vector<ll>(n)); 

    for (int i = 0; i < n; ++i) {
        int open = 0;
        bool fail = false;
        for (int j = i; j < n; ++j) {
            if (i < j) {
                pref_sum[i][j] += pref_sum[i][j-1];
            }

            if (s[j] == '(') ++open;
            else --open;

            if (open < 0) {
                fail = true;
            } else if (!fail && open == 0) {
                pref_sum[i][j]++;
            }
        }
    }


    for (int i = 0; i+1 < n; ++i) {
        f[i][i+1] = pref_sum[i][i+1];
    }
    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i+len-1 < n; ++i) {
            f[i][i+len-1] = f[i+1][i+len-1] + pref_sum[i][i+len-1];
        }
    }
    
    vector<vector<ll>> dp(n, vector<ll>(k)); 

    // O(n^3) dp
    for (int i = 1; i < n; ++i) {
        dp[i][0] = f[0][i];
        for (int x = 1; x < min(k, i); ++x) {
            // we are computing dp[i][x] here
            dp[i][x] = INF;
            
            for (int j = 0; j < i; ++j) {
                dp[i][x] = min(dp[i][x], dp[j][x-1] + f[j+1][i]);
            }
        }
    }

    cout << dp[n-1][k-1] << endl;

    return 0;
}