mickypinata

TOI10: Pairs of Four

Aug 5th, 2021
624
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1000;
  5.  
  6. char cards[N + 2];
  7. int dp[N + 2][N + 1];
  8.  
  9. int main(){
  10.  
  11.     int nCards;
  12.     scanf("%d", &nCards);
  13.     for(int i = 1; i <= nCards; ++i){
  14.         scanf(" %c", &cards[i]);
  15.     }
  16.     for(int d = 3; d <= nCards; ++d){
  17.         for(int l = 1; l <= nCards - d + 1; ++l){
  18.             int r = l + d - 1;
  19.             int ans = -1e9;
  20.             for(int i = l + 2; i <= r; ++i){
  21.                 if(cards[l] == cards[i]){
  22.                     ans = max(ans, 1 + dp[l + 1][i - 1] + dp[i + 1][r]);
  23.                 }
  24.             }
  25.             dp[l][r] = max(ans, dp[l + 1][r]);
  26.         }
  27.     }
  28.     cout << dp[1][nCards];
  29.  
  30.     return 0;
  31. }
  32.  
RAW Paste Data