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 #pragma GCC optimize ("O3") #include using namespace std; #define FOR(i, b, e) for(int i = (b); i < (e); i++) #define TRAV(x, v) for(auto &x: v) #define PB push_back #define SZ(x) ((int)x.size()) #define X first #define Y second using ll = long long; using vi = vector; using ii = pair; constexpr int INF = 0x3f3f3f3f; constexpr int N = 5324; int naw[N][N]; int dp[N][N]; void solve() { int n, k; string s; cin >> n >> k >> s; FOR(i, 0, n) { int bal = 0; FOR(j, i, n) { bal += (s[j] == '(' ? 1 : -1); if(bal < 0) break; naw[i + 1][j + 1] = bal == 0; } } for(int i = n; i >= 1; i--) FOR(j, i, n + 1) naw[i][j] += naw[i + 1][j] + naw[i][j - 1] - naw[i + 1][j - 1]; FOR(kk, 1, k + 1) dp[0][kk] = INF; FOR(i, 1, n + 1) dp[i][0] = INF; FOR(i, 1, n + 1) FOR(kk, 1, k + 1) { int akt = INF; FOR(j, 0, i) akt = min(akt, dp[j][kk - 1] + naw[j + 1][i]); dp[i][kk] = akt; } cout << dp[n][k] << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); // int tt; cin >> tt; // FOR(te, 0, tt) { // // cout << "Case #" << te + 1 << ": "; // solve(); // } solve(); return 0; }