Codeforces/667f.cpp at main · swati510/Codeforces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define int long long int
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define f(i,n) for(int i=0;i<n;i++)
#define forall(i,a,b) for(int i=a;i<b;i++)
#define INF 2147483647
using namespace std;
typedef  pair<int,int> pii;
typedef  vector<int>   vi;
typedef  vector<pii> vii;
int n,k;
string a,t;
int dp[3][205][205];
int go(int ind,int i,int k){
if(i==n){
    return 0;
}
int ans=0;
if(dp[ind][i][k]!=-1)return dp[ind][i][k];
if(t[ind]==a[i]){
    if(ind==1){
        ans=1+go(!ind,i+1,k);

    }
    else ans=go(!ind,i+1,k);
}
else{
    if(ind==1){
        if(k>0)ans=max(ans,1+go(!ind,i+1,k-1));
        ans=max(ans,go(ind,i,k));
    }
    else {
         if(k>0)ans=max(ans,go(!ind,i+1,k-1));
        ans=max(ans,go(ind,i,k));
        }
}
return dp[ind][i][k]=ans;
}
int32_t main()
{
  cin>>n>>k;
  cin>>a>>t;
  memset(dp,-1,sizeof(dp));
  int ans=go(0,0,k);
  cout<<ans<<endl;


    return 0;
}