mickypinata

SMMR-T109: Magic Spell III

Jul 26th, 2021
678
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 = 2000;
  5.  
  6. char str[N + 1];
  7. int dp[N + 1][N + 1];
  8.  
  9. int main(){
  10.  
  11.     scanf(" %s", str);
  12.     int len = strlen(str);
  13.     for(int i = 1; i <= len; ++i){
  14.         for(int j = 1; j <= len; ++j){
  15.             if(i != j && str[i - 1] == str[j - 1]){
  16.                 dp[i][j] = 1 + dp[i - 1][j - 1];
  17.             } else {
  18.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  19.             }
  20.         }
  21.     }
  22.     cout << dp[len][len];
  23.  
  24.     return 0;
  25. }
  26.  
RAW Paste Data