SRM526.5 Div2 Hard

1000
DPする。

class MagicNaming {
public:
  int maxReindeers(string M) 
  {
    const int N = 50 + 1;
    string ms[N][N];

    const int size = M.size();
    for (int i = 0; i < size; ++i) {
      for (int j = i; j <= size; ++j) {
        ms[i][j] = M.substr(i, j - i);
      }
    }

    int t[N][N];
    fill(&t[0][0], &t[N-1][N], -(1 << 20));
    for (int i = 1; i < N; ++i) {
      t[0][i] = 1;
    }
    
    for (int i = 0; i < size; ++i) {
      for (int j = i + 1; j < size; ++j) {
        for (int k = j + 1; k <= size; ++k) {          
          if (ms[i][j] + ms[j][k] <= ms[j][k] + ms[i][j]) {
            t[j][k] = max(t[j][k], t[i][j] + 1);
          }
        }
      }
    }
    
    int mx = 0;
    for (int i = 0; i < size; ++i) {
      mx = max(mx, t[i][size]);
    }
    return mx;
  }

};