SRM439 Div2 Hard

1000

dpするだけ。

view plainprint?

1. const int N = 50 + 1;  
2. int memo[N][N];  
3.   
4. string S;  
5.   
6. int rec(int i, int j)  
7. {  
8.   int &ret = memo[i][j];  
9.   if (ret != -1) return ret;  
10.   if (j <= i) return ret = 0;  
11.   
12.   int mn = 1 << 30;  
13.   
14.   mn = min(mn, rec(i + 1, j) + 1);  
15.   mn = min(mn, rec(i, j - 1) + 1);  
16.   mn = min(mn, rec(i + 1, j - 1) + (S[i] != S[j]));  
17.   
18.   return ret = mn;  
19. }  
20.   
21. class PalindromeFactory {  
22. public:  
23.   int getEditDistance(string ini)  
24.   {  
25.     S = ini;  
26.     const int size = S.size();  
27.   
28.     fill(&memo[0][0], &memo[N][0], -1);  
29.     int mn = rec(0, size - 1);  
30.   
31.     for (int i = 0; i < size; ++i) {  
32.       for (int j = i + 1; j < size; ++j) {  
33.         fill(&memo[0][0], &memo[N][0], -1);  
34.         swap(S[i], S[j]);  
35.         mn = min(mn, rec(0, size - 1) + 1);  
36.         swap(S[i], S[j]);  
37.       }  
38.     }  
39.     return mn;  
40.   }  
41. };  

const int N = 50 + 1;
int memo[N][N];

string S;

int rec(int i, int j)
{
  int &ret = memo[i][j];
  if (ret != -1) return ret;
  if (j <= i) return ret = 0;

  int mn = 1 << 30;

  mn = min(mn, rec(i + 1, j) + 1);
  mn = min(mn, rec(i, j - 1) + 1);
  mn = min(mn, rec(i + 1, j - 1) + (S[i] != S[j]));

  return ret = mn;
}

class PalindromeFactory {
public:
  int getEditDistance(string ini)
  {
    S = ini;
    const int size = S.size();

    fill(&memo[0][0], &memo[N][0], -1);
    int mn = rec(0, size - 1);

    for (int i = 0; i < size; ++i) {
      for (int j = i + 1; j < size; ++j) {
        fill(&memo[0][0], &memo[N][0], -1);
        swap(S[i], S[j]);
        mn = min(mn, rec(0, size - 1) + 1);
        swap(S[i], S[j]);
      }
    }
    return mn;
  }
};