Saleh127

Light OJ 1159 / DP

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