# TOI10: Pair of Fours

Dec 29th, 2020 (edited)
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. char ar[1010];
6. int n;
7. int dp[1010][1010];
8.
9. int recur(int i, int j){
10.     if(i == j or j < i) return dp[i][j] = 0;
11.     if(dp[i][j] != 0) return dp[i][j];
12.     if(ar[i] == ar[j]) return dp[i][j] = 1 + recur(i+1, j-1);
13.     if(i + 1 == j) return 0;
14.     for(int k=i;k<j;k++){
15.         dp[i][j] = max(dp[i][j], recur(i, k) + recur(k+1, j));
16.     }
17.     return dp[i][j];
18. }
19.
20. int main(){
21.
22.     scanf("%d", &n);
23.
24.     for(int i=1;i<=n;i++) scanf(" %c", &ar[i]);
25.
26.     for(int i=n;i>=1;i--){
27.         for(int j=i+1;j<=n;j++){
28.             if(i == j or j < i) dp[i][j] = 0;
29.             if(ar[i] == ar[j]) dp[i][j] = 1 + dp[i+1][j-1];
30.             if(i + 1 == j) dp[i][j] = 0;
31.             else{
32.                 for(int k=i;k<j;k++){
33.                     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
34.                 }
35.             }
36.         }
37.     }
38.
39.     printf("%d", dp[1][n]);
40.     //printf("%d", recur(1, n));
41.
42.     return 0;
43. }
RAW Paste Data Copied