fork download
copy 
  1.     #include <iostream>
  2.     #include <cstring>
  3.  
  4.     using namespace std;
  5.  
  6.     int dp[5001][5001];
  7.  
  8.     string eval(string s)
  9.     {
  10.     	string ans = "";
  11.     	ans += s[0];
  12.  
  13.     	for(int i = 1 ; i < s.length() ; i++)
  14.     	{
  15.     		if(s[i] != s[i - 1])
  16.     		{
  17.     			ans += s[i];
  18.     		}
  19.     	}
  20.  
  21.     	return ans;
  22.     }
  23.  
  24.     int lcs(string a, string b, int i, int j)
  25.     {
  26.     	if(i == a.length() && j == b.length())
  27.     	{
  28.     		return 0;
  29.     	}
  30.  
  31.     	if(dp[i][j] != -1)
  32.     	return dp[i][j];
  33.  
  34.     	if(i == a.length())
  35.     	{
  36.     		return dp[i][j] = lcs(a, b, i, j + 1);
  37.     	}
  38.  
  39.     	if(j == b.length())
  40.     	{
  41.     		return dp[i][j] = lcs(a, b, i + 1, j);
  42.     	}
  43.  
  44.     	if(a[i] == b[j])
  45.     	{
  46.     		return dp[i][j] = lcs(a, b, i + 1, j + 1) + 1;
  47.     	}
  48.  
  49.     	else
  50.     	{
  51.     		return dp[i][j] = max(lcs(a, b, i + 1, j), lcs(a, b, i, j + 1));
  52.     	}
  53.     }
  54.  
  55.     int main()
  56.     {
  57.     	//freopen("in.in", "r", stdin);
  58.  
  59.     	int t;
  60.     	cin >> t;
  61.  
  62.     	while(t--)
  63.     	{
  64.     		/**dp = new int [5001];
  65.     		for(int i = 0 ; i < 5001 ; i++)
  66.     		dp[i] = new int [5001];
  67.     		*/
  68.     		memset(dp, -1, sizeof(int) * 5001 * 5001);
  69.  
  70.  
  71.     		int n, m;
  72.     		cin >> n >> m;
  73.  
  74.     		string a, b;
  75.     		cin >> a >> b;
  76.  
  77.     		a = eval(a);
  78.     		b = eval(b);
  79.  
  80.     		cout << a.length() + b.length() - lcs(a, b, 0, 0) << endl;
  81.  
  82.     		/*
  83.     		for(int i = 0 ; i < 5001 ; i++)
  84.     		delete [] dp[i];
  85.     		
  86.     		delete [] dp;
  87.     		*/
  88.     	}
  89.     }
Success #stdin #stdout 0s 112960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/usz0Qb
language:
C++14 (gcc 8.3)
created:
6 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!