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;
- }
- };
0 件のコメント :
コメントを投稿