Saleh127

UVA 111 / DP - LCS

Dec 7th, 2021
762
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-07-23.13.21
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll dp[25][25];
  13.  
  14. int main()
  15. {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.  
  20.     ll n,m,i,j,k,l;
  21.  
  22.     cin>>n;
  23.  
  24.     ll a[n+4];
  25.     ll b[n+4];
  26.  
  27.     for(i=0; i<n; i++)
  28.     {
  29.         cin>>m;
  30.         a[m-1]=i+1;
  31.     }
  32.  
  33.  
  34.     while(cin>>m)
  35.     {
  36.         memset(dp,0,sizeof dp);
  37.  
  38.         b[m-1]=1;
  39.        
  40.         for(i=1; i<n; i++)
  41.         {
  42.             cin>>m;
  43.             b[m-1]=i+1;
  44.         }
  45.  
  46.  
  47.         for(i=1; i<=n; i++)
  48.         {
  49.             for(j=1; j<=n; j++)
  50.             {
  51.                 if(a[i-1]==b[j-1])
  52.                 {
  53.                     dp[i][j]=1+dp[i-1][j-1];
  54.                 }
  55.                 else
  56.                 {
  57.                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  58.                 }
  59.             }
  60.         }
  61.  
  62.         cout<<dp[n][n]<<endl;
  63.     }
  64.  
  65.     get_lost_idiot;
  66. }
  67.  
RAW Paste Data