Saleh127

UVA 10066 / DP - LCS

Dec 1st, 2021
1,041
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-02-01.34.03
  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[105][105];
  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,cc=0;
  21.  
  22.     while(cin>>n>>m && (n+m))
  23.     {
  24.         ll a[n+4],i,j;
  25.         ll b[m+4];
  26.  
  27.  
  28.         for(i=0;i<n;i++) cin>>a[i];
  29.         for(i=0;i<m;i++) cin>>b[i];
  30.  
  31.         memset(dp,0,sizeof dp);
  32.  
  33.         for(i=1; i<=n; i++)
  34.         {
  35.             for(j=1; j<=m; j++)
  36.             {
  37.                 if(a[i-1]==b[j-1])
  38.                 {
  39.                     dp[i][j]=dp[i-1][j-1]+1;
  40.                 }
  41.                 else
  42.                 {
  43.                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  44.                 }
  45.             }
  46.         }
  47.  
  48.         cout<<"Twin Towers #"<<++cc<<nl;
  49.         cout<<"Number of Tiles : "<<dp[n][m]<<nl<<nl;
  50.  
  51.  
  52.     }
  53.  
  54.  
  55.  
  56.     get_lost_idiot;
  57. }
  58.  
RAW Paste Data