LightOJ - 1033 - Generating Palindromes

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. const int S = 100003;
5. const int MOD = 1000000007;
6. int _I(){int x; scanf("%d", &x); return x;}
7. LL _LL(){LL x; scanf("%lld", &x); return x;}
8. int dirX[]={1, 0, -1, 0, 1, -1, 1, -1};
9. int dirY[]={0, 1, 0, -1, 1, -1, -1, 1};
10. int rX[] = {1, 1, 2, 2, -1, -1, -2, -2};
11. int rY[] = {2, -2, 1, -1, 2, -2, 1, -1};
12.  
13. int sset(int N, int pos){return N=N|(1<<pos);}
14. bool check(int N, int pos){return (bool)(N&(1<<pos));}
15. int reset(int N, int pos){return N=N&~(1<<pos);}
16. ///...............Code Starts From Here...............///
17.  
18. char palin[101];
19. int dp[101][101];
20.  
21. int generatePalin(int low, int high){
22.     if(low >= high)return 0;
23.     if(dp[low][high] != -1)return dp[low][high];
24.     dp[low][high] = 0;
25.     if(palin[low] == palin[high])dp[low][high] = generatePalin(low+1, high-1);
26.     else dp[low][high] = min(1+generatePalin(low+1, high), 1+generatePalin(low, high-1));
27.     return dp[low][high];
28. }
29.  
30. void Do(){
31.     int t = _I(), cs = 0;
32.     while(t--){
33.         scanf("%s", palin);
34.         memset(dp, -1, sizeof(dp));
35.         int sz = strlen(palin)-1;
36.         int ans = generatePalin(0, sz);
37.         printf("Case %d: %d\n", ++cs, ans);
38.     }
39. }
40.  
41. int main(){
42.     Do();
43.     return 0;
44. }