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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,long long> PIL;
const int mod = 1e9+7;

string arr;
int ok[4005][4005];
int pref[4005];
int mi[4005][4005];
int cnt[4005][4005];
int dp[4005][4005];

void compute(int l, int r, int optl, int optr, int lvl){
    if(l > r) return;
    int mid = (l+r)/2;

    int best = dp[lvl-1][mid];
    int optm = optl;
    for(int i=optl;i<min(mid, optr+1);i++){
        if(dp[lvl-1][i]+cnt[i+1][mid] < best){
            best = dp[lvl-1][i]+cnt[i+1][mid];
            optm = i;
        }
    }
    //cout<<mid<<" "<<best<<" "<<dp[lvl-1][mid]<<endl;

    dp[lvl][mid] = best;
    compute(l, mid-1, optl, optm, lvl);
    compute(mid+1, r, optm, optr, lvl);
}

int main(){
    ios_base::sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    cin>>arr;
    for(char & x: arr){
        if(x == '(') x = 1;
        else x = -1;
    }

    for(int i=1;i<=n;i++) pref[i] = pref[i-1]+arr[i-1];
    for(int i=1;i<=n;i++){
        mi[i][i] = pref[i];
        for(int j=i+1;j<=n;j++) mi[i][j] = min(mi[i][j-1], pref[j]);
    }

    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(pref[i-1] == pref[j] && mi[i][j] == pref[j]) ok[i][j] = 1;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++) cnt[i][j] = cnt[i][j-1] + ok[i][j];
    }
    for(int i=n;i>0;i--){
        for(int j=i+1;j<=n;j++) cnt[i][j] += cnt[i+1][j];
    }

    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++) cout<<cnt[i][j]<<" ";
    //     cout<<endl;
    // }

    for(int i=1;i<=n;i++) dp[1][i] = cnt[1][i];
    for(int i=2;i<=k;i++) compute(1, n, 0, n, i);

    // for(int i=1;i<=k;i++){
    //     for(int j=1;j<=n;j++) cout<<dp[i][j]<<" ";
    //     cout<<endl;
    // }

    cout<<dp[k][n]<<endl;
}