fork(2) download
copy 
  1. #include <cstring>
  2. #include <string>
  3. #include <map>
  4. #include <deque>
  5. #include <queue>
  6. #include <stack>
  7. #include <sstream>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <cstdio>
  11. #include <cmath>
  12. #include <algorithm>
  13. #include <vector>
  14. #include <set>
  15. #include <list>
  16. #include <climits>
  17.  
  18. using namespace std;
  19.  
  20. #define MAX 1005
  21.  
  22. int DP[MAX][MAX];
  23. string X, Y;
  24.  
  25. #define SET(DP, MAX) memset(DP, -1, sizeof(DP))
  26.  
  27. int Minimize(int i, int j, int end_x, int end_y){
  28.     if(i > end_x || j > end_y) return 0;
  29. 	if(DP[i][j] != -1) return DP[i][j];
  30. 	int res;
  31. 	if(X[i] == Y[j]) res = Minimize(i+1, j+1, end_x, end_y);
  32. 	else res = 1 + min(min(Minimize(i, j+1, end_x, end_y), Minimize(i+1, j, end_x, end_y)), Minimize(i+1, j+1, end_x, end_y));
  33. 	return DP[i][j] = res;
  34. }
  35.  
  36. int main(){
  37. //	freopen("in.txt", "r", stdin);
  38. 	SET(DP, -1);
  39. 	int LX;
  40. 	while(scanf("%d", &LX) != EOF){
  41. 		cin.ignore(); getline(cin, X);
  42. 		int LY; scanf("%d", &LY);
  43. 		cin.ignore(); getline(cin, Y);
  44. 		printf("%d\n", Minimize(0, 0, X.size()-1, Y.size()-1));
  45. 		SET(DP, -1);
  46. 	}
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 7284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DgLr4E
language:
C++ (gcc 8.3)
created:
10 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!