[UVA] 12473 - Common Palindrome

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12473 - Common Palindrome
Source            : UVA Online Judge
Category          : Dynamic Programing
Algorithm         : Dynamic Programing 
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define max3(a, b, c)         max(a, max(b, c))  
6.   
7. static const int maxn = 62;  
8.   
9. string A, B;  
10. int lenA, lenB;  
11.   
12. int dp[maxn][maxn][maxn][maxn];  
13. bool memoize[maxn][maxn][maxn][maxn];  
14.   
15. int solve(int i, int j, int k, int l)  
16. {  
17.       if (i > j || k > l) return 0;  
18.       if (i == j && (A[i] == B[k] || A[i] == B[l])) return 1;  
19.       if (k == l && (A[i] == B[k] || A[j] == B[k])) return 1;  
20.       int &ret = dp[i][j][k][l];  
21.       bool &mem = memoize[i][j][k][l];  
22.       if (mem == 1) return ret;  
23.       mem = 1;  
24.       if (A[i] == A[j] && B[k] == B[l] && A[i] == B[k])  
25.       {  
26.             ret = 2 + solve(i+1, j-1, k+1, l-1);  
27.       }  
28.       else  
29.       {  
30.             int choice1 = solve(i+1, j, k, l);  
31.             int choice2 = solve(i+1, j, k+1, l);  
32.             int choice3 = solve(i+1, j, k, l-1);  
33.             int choice4 = solve(i+1, j, k+1, l-1);  
34.   
35.             int choice5 = solve(i, j-1, k, l);  
36.             int choice6 = solve(i, j-1, k+1, l);  
37.             int choice7 = solve(i, j-1, k, l-1);  
38.             int choice8 = solve(i, j-1, k+1, l-1);  
39.   
40.             int choice9 = solve(i, j, k+1, l);  
41.             int choice10 = solve(i+1, j, k+1, l);  
42.             int choice11 = solve(i, j-1, k+1, l);  
43.             int choice12 = solve(i+1, j-1, k+1, l);  
44.   
45.             int choice13 = solve(i, j, k, l-1);  
46.             int choice14 = solve(i+1, j, k, l-1);  
47.             int choice15 = solve(i, j-1, k, l-1);  
48.             int choice16 = solve(i+1, j-1, k, l-1);  
49.   
50.             int maxi = max(choice1, choice2);  
51.             maxi = max3(maxi, choice3, choice4);  
52.             maxi = max3(maxi, choice5, choice6);  
53.             maxi = max3(maxi, choice7, choice8);  
54.             maxi = max3(maxi, choice9, choice10);  
55.             maxi = max3(maxi, choice11, choice12);  
56.             maxi = max3(maxi, choice13, choice14);  
57.             maxi = max3(maxi, choice15, choice16);  
58.   
59.             ret = maxi;  
60.       }  
61.       return ret;  
62. }  
63.   
64. int main()  
65. {  
66.       ios_base::sync_with_stdio(false);  
67.       cin.tie(NULL);  
68.       cout.tie(NULL);  
69.   
70.       int tc;  
71.       cin >> tc;  
72.       for (int tcase = 1; tcase <= tc; tcase++)  
73.       {  
74.             cin >> A >> B;  
75.             lenA = A.length();  
76.             lenB = B.length();  
77.             memset(memoize, 0, sizeof memoize);  
78.             cout << "Case " << tcase << ": " << solve(0, lenA-1, 0, lenB-1) << '\n';  
79.       }  
80. }