Advertisement
YEZAELP

SMMR-109: Magic Spell III

Jun 30th, 2020
104
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string str;
  5. int n;
  6. int main(){
  7.  
  8.     cin>>str;
  9.     n = str.size();
  10.     int dp[n+1][n+1];
  11.  
  12.     for(int i=n;i>=0;i--){
  13.         for(int j=n;j>=0;j--){
  14.             if(i==n or j==n) dp[i][j] = 0;
  15.             else if(i != j and str[i] == str[j]) dp[i][j] = 1 + dp[i+1][j+1];
  16.             else if(i+1 <= n and j+1 <= n) dp[i][j] = max(dp[i][j+1], dp[i+1][j]);
  17.             else if(i+1 > n) dp[i][j] = dp[i][j+1];
  18.             else if(j+1 > n) dp[i][j] = dp[i+1][j];
  19.         }
  20.     }
  21.  
  22.     printf("%d",dp[0][0]);
  23.  
  24.     return 0;
  25. }
Advertisement
RAW Paste Data Copied
Advertisement