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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <cstdio>
#include <vector>

#define DBG(X)

using namespace std;

char naw[100001];


int stos[100001];

vector<int> ret;

int pre[4001][4001];

int dp[4001][4001];

int main()
{
  int n, k;
  scanf("%d %d", &n, &k);
  
  scanf("%s", naw);
  
  
  
  
  for (int k = 0; k < n; k++)
  {
    int acc = 0;
    int pref = 0;
    for (int i = k; i < n; i++)
    {
      if (naw[i] == ')')
      {
        if (pref > 0)
        {
          for (int s = pref + 1; s <= n; s++) stos[s] = 0;
          if (stos[pref + 1])
          {
            ret.push_back(stos[pref + 1] * (stos[pref + 1] + 1) / 2);
            
            stos[pref + 1] = 0;
          }
          acc -= stos[pref] * (stos[pref] + 1) / 2;
          stos[pref]++;
          acc += stos[pref] * (stos[pref] + 1) / 2;
/*          printf("k %d i %d acc %d\n",k, i, acc);
          for (int l = 0; l < n; l++)
          {
            printf("%d ", stos[l]);
          }
          printf("\n");*/
        }
        pref--;
        if (pref >= 0)
        {
        }
        else
        {
          for (int s = 0; s <= n; s++) stos[s] = 0;
          int j = 1;
          while (stos[j] > 0)
          {
            ret.push_back(stos[j] * (stos[j] + 1) / 2);
            stos[j] = 0;
            j++;
          }
          pref = 0;
        }
      }
      else 
      {
        pref++;
      }
      
      //for (int s = 0; s < ret.size(); s++)
        //pre[k][i] += ret[s];
      //for (int s = 0; s < n; s++)
        //pre[k][i] += stos[s] * (stos[s] + 1) / 2;
      pre[k][i] = acc;
    }
    for (int s = 0; s <= n; s++) stos[s] = 0;
    
    /*printf("ret\n");
    for (int i = 0; i < ret.size(); i++)
    {
      printf("%d ", ret[i]);
    }
    printf("\n");

    for (int i = 0; i < 10; i++)
    {
      printf("stos %d\n", stos[i]);
    }
    printf("stos_id %d\n", stos_id);*/
    //int j = stos_id;
    //while (stos[j] > 0)
    {
      //ret.push_back(stos[j] * (stos[j] + 1) / 2);
      //stos[j] = 0;
      //j--;
    }
    ret.clear();
    /*for (int i = 0; i < ret.size(); i++)
    {
      printf("%d ", ret[i]);
    }*/
  }
  
  
  for (int i = 0; i < n; i++)
  {
    for (int j = i; j < n; j++)
    {
      DBG(printf("(%d %d %d)\n",i, j, pre[i][j]);)
    }
  }
  
  for (int i = 0; i < n; i++)
  {
    dp[i][0] = pre[0][i];
  }

  for (int i = 0; i < k; i++)
  {
    dp[0][i] = 0;
  }



  for (int j = 1; j < k; j++)
  {
    for (int i = 1; i < n; i++)
    {
      dp[i][j] = 1000000000;
      for (int l = 0; l < i; l++)
      {
        dp[i][j] = min(dp[l][j - 1] + pre[l + 1][i], dp[i][j]);
      }
    }
  }

  DBG(printf("dp\n");
  for (int i = 0; i < k; i++)
  {
    for (int j = 0; j < n; j++)
    {
      printf("%d %d %d\n", i, j, dp[j][i]);
    }
  })
  printf("%d\n", dp[n - 1][k - 1]);
  
  
  return 0;
}