# CodeChef STRMRG String Merging （dp）

## Description

All submissions for this problem are available.

Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

For a string S, let’s define a function F(S) as the minimum number of blocks consisting of consecutive identical characters in S. In other words, F(S) is equal to 1 plus the number of valid indices i such that Si ≠ Si+1.

You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.

Compute the minimum possible value of F(C).

## Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space-separated integers N and M.

The second line contains a single string A with length N.

The third line contains a single string B with length M.

## Output

For each test case, print a single line containing one integer — the minimum possible value of F(C).

## Constraints

1 ≤ T ≤ 100

1 ≤ N, M ≤ 5,000

1 ≤ sum of N in all test cases ≤ 5,000

1 ≤ sum of M in all test cases ≤ 5,000

strings A, B consist only of lowercase English letters

## Example Input

1
4 4
abab
baba


## Example Output

5


## 思路

unique 以后直接做 LCS 即可。

## AC 代码

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0);
using namespace std;
const int maxn = 1e4+10;
const int mod = 1e9+7;
typedef long long LL;

int n,m;
char s1[maxn],s2[maxn];
int dp[maxn][maxn];

int unique_str(char *s,int len)
{
int tot = 0;
for(int i=1; i<len; i++)
if(s[i]!=s[tot])
s[++tot] = s[i];
}

int main()
{
IO;
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
cin>>(s1+1);
cin>>(s2+1);
n = unique_str(s1+1,n);
m = unique_str(s2+1,m);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(s1[i]==s2[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<n+m-dp[n][m]<<endl;
}
return 0;
}