fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s1,s2;
  4. int dp[1000][1000];
  5. int wt_i,wt_d,wt_m;
  6. int m,n;
  7. int ED(int i,int j)
  8. {
  9. if(i==m) 
  10. {
  11. return n-j;
  12. }
  13. if(j==n)
  14. {
  15. return m-i;
  16. }
  17. if(dp[i][j]!=-1)
  18. return dp[i][j];
  19. if(s1[i]==s2[j])
  20. {
  21.  
  22.  
  23. return dp[i][j]=ED(i+1,j+1);
  24. }
  25. else
  26. {
  27.  
  28. int ins=wt_i+ED(i,j+1);
  29. int del=wt_d+ED(i+1,j);
  30. int mod=wt_m+ED(i+1,j+1);
  31. return dp[i][j]=min(ins,min(del,mod));
  32.  
  33. }
  34. }
  35.  
  36. int main()
  37. {
  38. cin>>s1>>s2;
  39. cin>>wt_i>>wt_d>>wt_m;
  40. m=s1.size();
  41. n=s2.size();
  42. memset(dp,-1,sizeof(dp));
  43. int ans=ED(0,0);
  44. cout<<ans<<endl;
  45. }
Success #stdin #stdout 0.01s 7516KB
comments (?)
stdin
copy 
abc
bc
stdout
copy 
0
https://ideone.com/vBbKSo
language:
C++ (gcc 8.3)
created:
13 days 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!