fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <queue>
  7. #include <stack>
  8. #include <string>
  9. #include <cstring>
  10. #include <cmath>
  11. #include <map>
  12. #include <vector>
  13. #include <array>
  14. #include <set>
  15. #include <climits>
  16. #include <sstream>
  17. #include <iomanip>
  18. #include <cassert>
  19. #include <bitset>
  20. #include <numeric>
  21. using namespace std;
  22. #define MOD 1000000007
  23. #define MAXN 2002
  24. long long dp[MAXN][MAXN];
  25. string a , b; 
  26. int n;
  27. int edit(int current_a_index , int current_b_index){
  28.     if((int)a.size()==current_a_index && (int)b.size()==current_b_index){
  29.         return 0;
  30.     }
  31.     if((int)a.size()==current_a_index){
  32.         return n*(b.size()-current_b_index);
  33.     }
  34.     if((int)b.size()==current_b_index){
  35.         return n*(a.size()-current_a_index);
  36.     }
  37.     if(dp[current_a_index][current_b_index]!=-1){
  38.         //cerr<<"found in dp"<<endl;
  39.         return dp[current_a_index][current_b_index];
  40.     }
  41.     return dp[current_a_index][current_b_index]=min({edit(current_a_index+1,current_b_index+1)+abs(a[current_a_index]-b[current_b_index]),edit(current_a_index+1,current_b_index)+n,edit(current_a_index,current_b_index+1)+n});
  42. }
  43. int main(void){
  44. #ifdef HELL_JUDGE
  45.     freopen("input","r",stdin);
  46.     freopen("output","w",stdout);
  47.     freopen("error","w",stderr);
  48. #endif 
  49.     cin>>a>>b;
  50.     memset(dp ,-1 , sizeof(dp));
  51.     cin>>n;
  52.     cout<<edit(0,0)<<endl;
  53.     return 0;
  54. }
Success #stdin #stdout 0.01s 34832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/IsaTcD
problem MBLAST, based on SPOJ submission 25484143 (CPP14), 2020-03-02 18:26:21
language:
C++14 (gcc 8.3)
created:
4 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!