fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. int T,N,M,K,dp[110][110][110]; char a[110],b[110];
  6.  
  7. int solve(int i, int j, int k){
  8.     if (k==0) return 0;
  9.     if (i==0 || j==0) return -(1<<30);
  10.     if (dp[i][j][k]!=-1) return dp[i][j][k];
  11.  
  12.     int &ret=dp[i][j][k];
  13.     ret=-(1<<30);
  14.     if (a[i]==b[j]) ret=max(ret,a[i]+solve(i-1,j-1,k-1));
  15.     ret=max(ret,solve(i-1,j,k));
  16.     ret=max(ret,solve(i,j-1,k));
  17.  
  18.     return ret;
  19. }
  20.  
  21. int main(){
  22.     cin >> T;
  23.  
  24.     int res;
  25.     while (T--){
  26.         cin >> (a+1);
  27.         a[0]='.';
  28.         cin >> (b+1);
  29.         b[0]='.';
  30.         N=strlen(a)-1;
  31.         M=strlen(b)-1;
  32.         cin >> K;
  33.         memset(dp,-1,sizeof(dp));
  34.  
  35.         res=solve(N,M,K);
  36.         if (res<0) res=0;
  37.         cout << res << "\n";
  38.     }
  39.  
  40.     return 0;
  41. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tI8d2a
language:
()
created:
9 years ago
visibility:
secret

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!