Advertisement
Saleh127

UVA 10192 / DP - LCS

Dec 1st, 2021
575
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-01-20.24.47
  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[1005][1005];
  13.  
  14. int main()
  15. {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.  
  20.     string a;
  21.     string b;
  22.  
  23.     ll s=0;
  24.  
  25.     while(getline(cin,a))
  26.     {
  27.         if(a=="#") break;
  28.  
  29.         getline(cin,b);
  30.  
  31.         ll n,m,i,j,k,l;
  32.  
  33.         n=a.size();
  34.         m=b.size();
  35.  
  36.         memset(dp,0,sizeof dp);
  37.  
  38.         for(i=1; i<=n; i++)
  39.         {
  40.             for(j=1; j<=m; j++)
  41.             {
  42.                 if(a[i-1]==b[j-1])
  43.                 {
  44.                     dp[i][j]=dp[i-1][j-1]+1;
  45.                 }
  46.                 else
  47.                 {
  48.                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  49.                 }
  50.             }
  51.         }
  52.  
  53.  
  54.         cout<<"Case #"<<++s<<": you can visit at most "<<dp[n][m]<<" cities."<<nl;
  55.  
  56.     }
  57.  
  58.     return 0;
  59. }
  60.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement