SRM526.5 Div2 Hard

1000
DPする。

view plainprint?

1. class MagicNaming {  
2. public:  
3.   int maxReindeers(string M)   
4.   {  
5.     const int N = 50 + 1;  
6.     string ms[N][N];  
7.   
8.     const int size = M.size();  
9.     for (int i = 0; i < size; ++i) {  
10.       for (int j = i; j <= size; ++j) {  
11.         ms[i][j] = M.substr(i, j - i);  
12.       }  
13.     }  
14.   
15.     int t[N][N];  
16.     fill(&t[0][0], &t[N-1][N], -(1 << 20));  
17.     for (int i = 1; i < N; ++i) {  
18.       t[0][i] = 1;  
19.     }  
20.       
21.     for (int i = 0; i < size; ++i) {  
22.       for (int j = i + 1; j < size; ++j) {  
23.         for (int k = j + 1; k <= size; ++k) {            
24.           if (ms[i][j] + ms[j][k] <= ms[j][k] + ms[i][j]) {  
25.             t[j][k] = max(t[j][k], t[i][j] + 1);  
26.           }  
27.         }  
28.       }  
29.     }  
30.       
31.     int mx = 0;  
32.     for (int i = 0; i < size; ++i) {  
33.       mx = max(mx, t[i][size]);  
34.     }  
35.     return mx;  
36.   }  
37.   
38. };  

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;
  }

};