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
82
83
84
85
86
87
88
89
90
91
92
93
94
// Jakub Rozek
// Nawiasy
// PA 2022 B r5
// czas: n^2*log(n) + k*n*log(n)
// pami: n^2

#include "bits/stdc++.h"
using namespace std;

const int N=4003;
const int INFi=1000000009;
const long long INF=1000000000000000018;

long long n,k,R=1;
string s;
long long tree[N*4];
long long nawt[N][N];
long long dp[2][N];

int minwar(int w, int a, int b, int c, int d)
{
    if(a>d || b<c) return INFi;
    if(c<=a && b<=d) return tree[w];
    return min(minwar(w*2,a,(a+b)/2,c,d),minwar(w*2+1,(a+b)/2+1,b,c,d));
}

long long naw(int a, int b)
{
    return nawt[a][b];
}

void licz(int l, int a, int b, int p, int k)
{
    if(a>b) return;
    
    int c=(a+b)/2, sr=p, nawiasy;
    
    dp[l][c]=INF;
    for(int j=p; j<min(c,k); ++j)
    {
        nawiasy=naw(j+1,c);
        if(dp[1-l][j]+nawiasy<dp[l][c])
        {
            dp[l][c]=dp[1-l][j]+nawiasy;
            sr=j;
        }
    }

    licz(l,a,c-1,p,sr+1);
    licz(l,c+1,b,sr,k);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long a,b,c;

    cin>>n>>k>>s;
    while(R<n) R*=2;

    a=0;
    for(int i=0; i<n; ++i)
    {
        if(s[i]=='(') ++a;
        else --a;
        tree[R+i+1]=a;
    }
    for(int i=R-1; i>0; --i) tree[i]=min(tree[i*2],tree[i*2+1]);
    
    for(int d=1; d<n; ++d)
    {
        a=0;b=a+d;
        while(b<n)
        {
            nawt[a][b]=nawt[a+1][b]+nawt[a][b-1]-nawt[a+1][b-1];
            if(tree[R+a]==tree[R+b+1])
            {
                c=minwar(1,0,R-1, a,b);
                if(c>=tree[R+a]) nawt[a][b]++;
            }
            ++a;
            ++b;
        }
    }

    for(int i=0; i<n; ++i) dp[1][i]=naw(0,i);
    for(int l=2; l<=k; ++l) licz(l%2,0,n-1,0,n);

    cout<<dp[k%2][n-1]<<"\n";

    return 0;
}