fork download
copy 
  1. //doing with memoriziation
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<algorithm>
  5. #include<string.h>
  6. #include<vector>
  7. #define inf 1000000
  8. #define lli long long int
  9. char buf[1000];
  10. char buf1[1000];
  11. lli k,add,del,rem;
  12. int arr[40][40];
  13. lli min1(lli a,lli b)
  14. {
  15.   if(a<b)
  16.     return a;
  17.   else
  18.     return b;
  19. }
  20.  
  21. lli minimum(lli a,lli b,lli c)
  22. {
  23.   return min1(min1(a,b),c);
  24. }
  25.  
  26.  
  27. lli edit_dis(char *buf,char*buf1,lli m,lli n,lli add1,lli del1,lli rem1)
  28. {
  29.   if(add1+del1+rem1>k)//if edit is greater than k return inf
  30.    return inf;
  31.   if(m==0 && n==0)
  32.   {
  33.     return 0;
  34.   }
  35.   if(m==0 && n<k)
  36.     return n;
  37.   if(m==0 && n>k)//if edit is greater than k return inf
  38.     return inf;
  39.   if(n==0 && m<k)
  40.     return m;
  41.   if(n==0 && m>k)//if edit is greater than k return inf
  42.     return inf;
  43.   if(arr[m][n]!=-1)
  44.   {
  45.     return arr[m][n];
  46.   }
  47.   lli left;
  48.   if(arr[m-1][n]!=-1)
  49.   {
  50.     left=arr[m-1][n]+add;
  51.     add1=add+add1;
  52.   }
  53.   else
  54.   {
  55.      add1=add+add1;
  56.      left=edit_dis(buf,buf1,m-1,n,add1,del1,rem1)+add;
  57.   }
  58.  
  59.  
  60.   lli right;
  61.   if(arr[m][n-1]!=-1)
  62.   {
  63.     right=arr[m][n-1]+del;
  64.     del1=del1+del;
  65.   }
  66.   else
  67.   {
  68.      del1=del+del1;
  69.      right=edit_dis(buf,buf1,m,n-1,add1,del1,rem1)+del;
  70.   }
  71.  
  72.   lli corner;
  73.   if(arr[m-1][n-1]!=-1)
  74.   {
  75.     corner=arr[m-1][n-1]+rem*(buf[m-1]!=buf1[n-1]);
  76.     rem1=rem1+rem;
  77.   }
  78.   else
  79.   {
  80.      rem1=rem1+rem;
  81.      corner=edit_dis(buf,buf1,m-1,n-1,add1,del1,rem1)+rem*(buf[m-1]!=buf1[n-1]);
  82.   }
  83.  
  84.   return arr[m][n]=minimum(right,left,corner);
  85. }
  86. void my_memset()
  87. {
  88.   lli i,j;
  89.   for(i=0;i<40;i++)
  90.   {
  91.     for(j=0;j<40;j++)
  92.      arr[i][j]=-1;
  93.   }
  94. }
  95. int main()
  96. {
  97.   lli t;
  98.   scanf("%lld",&t);
  99.   getchar_unlocked();
  100.   while(t--)
  101.   {
  102.     my_memset();
  103.     scanf("%s",buf);
  104.     getchar_unlocked();
  105.     scanf("%s",buf1);
  106.     getchar_unlocked();
  107.     scanf("%lld%lld%lld",&add,&rem,&k);
  108.     del=add;
  109.     lli m=strlen(buf);
  110.     lli n=strlen(buf1);
  111.     lli ans=edit_dis(buf,buf1,m,n,0,0,0);
  112.     printf("ans====%lld\n",ans);
  113.   }
  114. }
  115.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:4:20: fatal error: algorithm: No such file or directory
 #include<algorithm>
                    ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/LOcv6I
language:
C (gcc 8.3)
created:
9 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!