解いた問題

2/28/2012

SRM526.5 Div2 Hard

1000
DPする。
  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. };  

0 件のコメント :

コメントを投稿