fork download
copy 
  1. /// Accepted
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define mx 102
  5. int dp[mx][mx][mx];
  6. char a[mx],b[mx],c[mx];
  7. int lena, lenb, lenc;
  8. int fun(int ida, int idb, int idc)
  9. {
  10.     if(ida>=lena || idb>=lenb){
  11.         if(idc>=lenc)
  12.             return 0;
  13.         else return -500;
  14.     }
  15.     if(dp[ida][idb][idc]!=-1) return dp[ida][idb][idc];
  16.     int ret = 0;
  17.     if(idc==0){
  18.         if(a[ida]==b[idb]){
  19.             if(a[ida]==c[idc]){
  20.                 ret = 1 + fun(ida+1, idb+1, idc+1);
  21.                 ret = max(ret, 1 + fun(ida+1, idb+1, idc));
  22.             }
  23.             else{
  24.                 ret = 1 + fun(ida+1, idb+1, idc);
  25.             }
  26.         }
  27.         else{
  28.             ret = fun(ida+1, idb, idc);
  29.             ret = max(ret, fun(ida, idb+1, idc));
  30.         }
  31.     }
  32.     else if(idc==lenc){
  33.         if(a[ida]==b[idb]){
  34.             ret = 1 + fun(ida+1, idb+1, idc);
  35.         }
  36.         else{
  37.             ret = fun(ida+1, idb, idc);
  38.             ret = max(ret, fun(ida, idb+1, idc));
  39.         }
  40.     }
  41.     else{
  42.         if(a[ida]==b[idb]){
  43.             if(a[ida]==c[idc]){
  44.                 ret = 1 + fun(ida+1, idb+1, idc+1);
  45.             }
  46.             else{
  47.                 ret = fun(ida+1, idb+1, idc);
  48.             }
  49.         }
  50.         else{
  51.             ret = fun(ida+1, idb, idc);
  52.             ret = max(ret, fun(ida, idb+1, idc));
  53.         }
  54.     }
  55.     return dp[ida][idb][idc] = ret;
  56. }
  57. int main()
  58. {
  59.     int tc;
  60.     scanf("%d",&tc);
  61.     for(int t=1; t<=tc; t++){
  62.         scanf("%s%s%s",a,b,c);
  63.         lena = strlen(a);
  64.         lenb = strlen(b);
  65.         lenc = strlen(c);
  66.         memset(dp,-1,sizeof dp);
  67.         printf("Case %d: %d\n",t,max(0,fun(0,0,0)));
  68.     }
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 7172KB
comments (?)
stdin
copy 
2

AB
AB
A

AAA
AAB
A
stdout
copy 
Case 1: 2
Case 2: 2
https://ideone.com/5bo1nl
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!