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

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int Min[4009][4009];
bool tab[4009];
int pre[4009];
int dp2[4009][4009];
int C[4009][4009];
int dp_cur[4009];
int dp_pre[4009];

bool czy(int x, int y) {
	if(x == 0) {
		return pre[y]==0 and Min[x][y]>=0;
	}
	if(pre[y]-pre[x-1]) return false;
	if(Min[x][y]-pre[x-1]<0) return false;
	return true;
}

void compute(int l, int r, int optl, int optr) {
	if(l > r) return;
	int m = (l+r)/2;
	pii best = {1e9, -1};
	for(int k=optl;k<=min(m, optr);k++) {
		best = min(best, {(k?dp_pre[k-1]:0) + C[k][m], k});
	}
	dp_cur[m] = best.st;
	int opt = best.nd;
	compute(l, m-1, optl, opt);
	compute(m+1, r, opt, optr);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;
	cin >> n >> k;
	for(int i=0;i<n;i++) {
		char c;
		cin >> c;
		if(c == '(') tab[i] = true;
		if(i) pre[i] = pre[i-1];
		if(tab[i]) pre[i]++;
		else pre[i]--;
	}
	for(int i=0;i<n;i++) {
		Min[i][i] = pre[i];
		for(int j=i+1;j<n;j++) {
			Min[i][j] = min(Min[i][j-1], pre[j]);
		}
	}
	for(int i=0;i<n;i++) {
		for(int j=i-1;j>=0;j--) {
			dp2[i][j] = dp2[i][j+1];
			if(czy(j, i)) dp2[i][j]++;
		}
	}
	for(int i=0;i<n;i++) {
		for(int j=i+1;j<n;j++) {
			C[i][j] = C[i][j-1];
			C[i][j] += dp2[j][i];
		}
	}
	for(int i=0;i<n;i++) {
		dp_pre[i] = C[0][i];
	}
	for(int i=1;i<k;i++) {
		compute(0, n-1, 0, n-1);
		for(int j=0;j<n;j++) dp_pre[j] = dp_cur[j];
	}
	cout << dp_pre[n-1] << "\n";
}