fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <iostream>
  3. using namespace std;
  4.  
  5.  
  6. int min(int x,int y)
  7. {
  8. 	return x>y?y:x;
  9. }
  10.  
  11.  
  12. vector<char>v1,v2;
  13. int dp[1000][1000];
  14. int main() {
  15. 	// your code goes here
  16. 	int t,l1,l2,i,j,p,cnt;
  17. 	char st1[1000],st2[1000];
  18. 	scanf("%d",&t);
  19. 	while(t--)
  20. 	{
  21. 	    scanf("%d%s%d%s",&l1,st1,&l2,st2);
  22. 	    i=1;
  23. 	    cnt=1;
  24. 	    while(cnt<=l1)
  25. 	    {
  26. 	        j=st1[i]-48;
  27. 	        for(p=0;p<j;p++)
  28. 	        v1.push_back(st1[i-1]);
  29. 	        i=i+2;
  30. 	        cnt++;
  31. 	    }
  32. 	  //  for(i=0;i<v1.size();i++)
  33. 	    //printf("%c",v1[i]);
  34. 	   // printf("\n");
  35. 	    i=1;
  36. 	    cnt=1;
  37. 	    while(cnt<=l2)
  38. 	    {
  39. 	        j=st2[i]-48;
  40. 	        for(p=0;p<j;p++)
  41. 	        v2.push_back(st2[i-1]);
  42. 	        i=i+2;
  43. 	        cnt++;
  44. 	    }
  45. 	   for(i=0;i<v1.size()+v2.size();i++)
  46. 	   {
  47. 	       dp[0][i]=i;
  48. 	       dp[i][0]=2*i;
  49. 	   }
  50. 	    //for(i=0;i<v2.size();i++)
  51. 	    //printf("%c",v2[i]);
  52. 	    for(i=1;i<=v1.size();i++)
  53. 	    {
  54. 	        for(j=1;j<=v2.size();j++)
  55. 	        {
  56. 	            //printf("\ni=%d j=%d @ %c %c\n",i,j,v1[i-1],v2[j-1]);
  57. 	            if(v1[i-1]==v2[j-1])
  58. 	            {
  59. 	               // printf("yes\n");
  60. 	               // printf("chk1\n");
  61. 	               dp[i][j]=dp[i-1][j-1];
  62. 	        //   printf("*%d\n",dp[i][j]);
  63. 	            }
  64.  
  65. 	            else
  66. 	            {
  67. 	              //  printf("chk2\n");
  68. 	                //printf("dp[i][j-1]=%d %d %d\n",dp[i][j-1],dp[i-1][j],1+max(dp[i][j-1],dp[i-1][j]));
  69. 	                dp[i][j]=min(1+dp[i][j-1],2+dp[i-1][j]);
  70. 	            // printf("$%d\n",dp[i][j]);
  71. 	            }
  72. 	        }
  73. 	    }
  74. 	    l1=v1.size();
  75. 	    l2=v2.size();
  76. 	    ///printf("l1=%d l2=%d\n",l1,l2);
  77. 	    printf("%d\n",dp[l1][l2]);
  78. 	    v1.clear();
  79. 	    v2.clear();
  80. 	}
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0s 6724KB
comments (?)
stdin
copy 
2
2 a3b2
1 b3
3 a1b1a1
1 a2
stdout
copy 
7
2
https://ideone.com/dkKV9D
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 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!