YEZAELP

TOI10: Pair of Fours

Dec 29th, 2020 (edited)
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None
  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