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
#include <bits/stdc++.h>
#define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr<<#x<<" "<<x<<endl
#define ll long long 
#define st first
#define nd second
using namespace std;

int n, k, res[303][303], dp[303][303], dobry[303][303];
string s;

void count(int l, int r) {
	if (r - l == 1) {
		if (s[l] == '(' && s[r] == ')') dp[l][r] = 1;
		else dp[l][r] = 0;
	}
	else if (l == r) dp[l][r] = 0;
	else {
		if (dp[l + 1][r] == -1) count(l + 1, r);
		if (dp[l][r - 1] == -1) count(l, r - 1);
		if (dp[l + 1][r - 1] == -1) count(l + 1, r - 1);
		dp[l][r] = dp[l][r - 1] + dp[l + 1][r] - dp[l + 1][r - 1] + dobry[l][r];
	}
	//cout << l << " " << r << " " << dp[l][r] << endl;
}

int main()
{
	qio;
	cin >> n >> k;
	cin >> s;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = -1;
			if (i == j) dp[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		bool zle = 0;
		int d = 0;
		for (int j = i; j < n; j++) {
			if (s[j] == '(') d++;
			else d--;
			if (d < 0) zle = 1;
			if (d == 0 && zle == 0) dobry[i][j] = 1;
		}
	}
	count(0, n - 1);

	for (int i = 1; i <= k; i++) {
		for (int j = i - 1; j < n; j++) {
			if (i == 1) res[i][j] = dp[0][j];
			else {
				res[i][j] = INT_MAX;
				for (int q = i - 2; q < j; q++) {
					res[i][j] = min(res[i][j], dp[q + 1][j] + res[i - 1][q]);
				}
			}
		}
	}
	cout << res[k][n - 1] << endl;
}