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

typedef long long int lli;

const int MAXN = 100'005;

char in[MAXN];
lli t[MAXN];
lli s[MAXN];

vector<lli> mins[MAXN];
vector<lli> par[MAXN];
vector<lli> res[MAXN];

lli is_perfect(int p, int k) {
	if (s[k-1] != s[p-1])
		return 0;
	
	return mins[p-1][k] == s[p-1];
}

int main() {
	int n, k;
	scanf("%d%d%*c", &n, &k);
	
	scanf("%s", in);
	
	for (int i=1; i<=n; i++) {
		if (in[i-1] == '(')
			t[i] = 1;
		else
			t[i] = -1;
		
		s[i] = s[i-1] + t[i];
	}
	
	mins[0].resize(n+5);
	par[0].resize(n+5);
	
	for (int i=0; i<=n; i++) {
		mins[i].resize(n+5);
		par[i].resize(n+5);
		mins[i][i+1] = s[i];
		
		for (int j=i+2; j<=n+1; j++)
			mins[i][j] = min(mins[i][j-1], s[j-1]);
	}
	
	for (int len=2; len<=n; len++) {
		for (int i=1; i+len <= n+1; i++) {
			int j = i + len;
			par[i][j] = par[i][j-1] + par[i+1][j] - par[i+1][j-1] + is_perfect(i, j);
		}
	}
	
	for (int i=1; i<=n; i++) {
		res[i].resize(min(i, k) + 5);
		res[i][1] = par[1][i+1];
		
// 		printf("i: %d\n", i);
// 		printf("(1 %lld) ", res[i][1]);
		
		for (int kk=2; kk<=min(i, k); kk++) {
			res[i][kk] = res[i-1][kk-1];
			for (int d=2; i-d>=kk-1; d++) {
				res[i][kk] = min(res[i][kk], res[i-d][kk-1] + par[i-d+1][i+1]);
			}
// 			printf("(%d %lld) ", kk, res[i][kk]);
		}
// 		printf("\n");
	}
	
	printf("%lld\n", res[n][k]);
	
// 	for (int i=1; i<=n; i++)
// 		printf("%lld ", s[i]);
// 	printf("\n");
// 	
// 	for (int i=1; i<=n; i++) {
// 		for (int j=i+1; j<=n+1; j++) {
// 			printf("(%d %d): %lld\n", i, j, par[i][j]);
// // 			printf("(%d %d): %lld\n", i, j, mins[i][j]);
// // 			printf("(%d %d): %lld\n", i, j, is_perfect(i, j));
// 		}
// 		printf("\n");
// 	}
	
	return 0;
}