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
#include <iostream>
#include <vector>
using namespace std;
using ll=long long;
const int C=4001;
const ll Inf = 1000000000000001ll;

//limit - to calcutate, border - feasible region for opt
ll dp[C][C], res[C][C];
void solve_dc_dp(int index, int left_limit, int right_limit, int left_border, int right_border){
	if (left_limit > right_limit) return;

	int position;
	int place = left_limit + (right_limit-left_limit)/2;
	res[index][place] = Inf;
	for (int i=left_border; i<=right_border; i++){
		ll value = res[index-1][i-1] + dp[i][place];
		if (value < res[index][place]){
		       	res[index][place] = value;
			position = i;
		}
	}

	solve_dc_dp(index, place+1, right_limit, position, right_border);
	solve_dc_dp(index, left_limit, place-1, left_border, position);
}

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

	int n, k;
	cin >> n >> k;
	cin >> expr;

	//Ku potomnych: zastąpić drzewem i skewencją, wyjdzie liniowy dostęp do dp(i, j) - przy nklog(n) ledwie istotne
	for (int i=n-1; i>=0; i--){
		bool dead = false;
		int current_results = 0;
		int plus_minus = 0;
		for (int j=i; j<n; j++){
			if (expr[j] == '(') plus_minus++;
			else plus_minus--;

			if (plus_minus < 0) dead = true;
			if (plus_minus == 0 && dead == false) current_results++;

			dp[i][j] = dp[i+1][j] + current_results;
		}
	}

	for (int i=0; i<n; i++) res[1][i] = dp[0][i];
	//Solucja?: https://codeforces.com/blog/entry/8219#comment-139241 - wzorcówka pewno
	for (int j=2; j<=k; j++){
		solve_dc_dp(j, 0, n-1, 0, n-1);
	}
	printf ("%lld\n", res[k][n-1]);

return 0;}