fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. #define mp make_pair 
  4. #define f(i,n) for(int i=0;i<n;i++) 
  5. #define F first 
  6. #define S second 
  7. #define pb push_back 
  8.  
  9. using namespace std;
  10.  
  11. ll a[1005] , b[1005];
  12.  
  13. ll cache[1005][1005];
  14.  
  15. ll n,m;
  16.  
  17. ll dp(ll x, ll y){
  18. 	if(x==n or y==m){
  19. 		return (n+m-x-y);
  20. 	}else if(cache[x][y]!=-1)
  21. 		return cache[x][y];
  22. 	else{
  23. 		ll val = min(dp(x+1,y),dp(x,y+1)) + 1;
  24. 		if(a[x]==b[y]){
  25. 			val = min(val, dp(x+1,y+1));
  26. 		}else{
  27. 			val = min(val,dp(x+1,y+1)+1);
  28. 		}
  29. 		cache[x][y] = val;
  30. 		return val;
  31. 	}
  32. }
  33.  
  34. void test(){
  35. 	memset(cache,-1,sizeof(cache));
  36. 	cin>>n>>m;
  37. 	f(i,n)cin>>a[i];
  38. 	f(i,m)cin>>b[i];
  39. 	cout<<dp(0,0)<<"\n";
  40. }
  41.  
  42. int main(){
  43. 	std::ios::sync_with_stdio(false);
  44. 	cin.tie(0);
  45. 	cout.tie(0);
  46. 	int tests=1;
  47. 	// cin>>tests;
  48. 	while(tests--){
  49. 		test();
  50. 	}
  51. }
  52.  
Success #stdin #stdout 0s 11388KB
comments (?)
stdin
copy 
4 3
1 2 1 3
1 3 1
stdout
copy 
2
https://ideone.com/Kl70pT
language:
C++14 (gcc 8.3)
created:
4 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!