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
#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)
#define LINE(n,x) char x[n]; fgets(x, n, stdin)

typedef long long LL;

const LL INF = 1000000000000000000LL;
const int N = 4000;
int h[N + 1];
LL x[N + 1][N + 1];
int y[N + 1][N + 1];
LL r[N + 1][N + 1];

int main() {
	INT(n);
	INT(k);
	scanf("\n");
	LINE(N+10, a);
	REP(i,n) h[i + 1] = h[i] + (a[i] == '(' ? 1 : -1);
	REP(i,n+1) y[i][i] = h[i];
	REP(i,n) FOR(j,i+1,n+1) y[i][j] = min(y[i][j - 1], h[j]);
	FOR(d,2,n+1) REP(i,n-d+1) {
		int j = i + d;
		x[i][j] = x[i + 1][j] + x[i][j - 1] - x[i + 1][j - 1];
		if (h[i] == y[i][j] && h[i] == h[j]) ++x[i][j];
	}
	FOR(i,1,n+1) r[i][0] = INF;
	FOR(i,1,n+1) FOR(kk,1,min(n,k)+1) {
		LL mi = INF;
		FOR(j,kk-1,i) mi = min(mi, r[j][kk-1] + x[j][i]);
		r[i][kk] = mi;
	}
	printf("%lld\n", r[n][k]);
}