贪心捏

题目大意

给三条字符串，只能在最后删除或添加字符 求最少多少次能使三条相同

考虑样例

输入样例：

3 CAT 3 TAC 5 CATCH

ans= 8

一眼丁真，看到CAT重复了两遍 显然改变CAT是最劣的 改变CAT所需的步骤是改变TAC的两倍 所以理应改变TAC （以下将最长的重复的部分称为 最长公共前缀）

CH直接删掉就好啦

可以看出来 对于重复的部分 我们不做任何处理是最优的 而对于剩下的那条“另类” 直接把他变成我们想要的样子就好了

而多余的部分 我们可以证明多余的部分一定是不同的或唯一的 否则它也是最长公共前缀的一部分了 设n1,n2为最长公共前缀所在的两部分的长度，最长公共前缀长度为ans1 那么可以直接把最终答案num=n1+n2-2ans1 而对于剩下的字符串来说 num+= n3(删掉全部的长度)+ans1(全部改成最长公共前缀)-ans22(可能与最长公共前缀有重复的部分得减去这部分)

个人认为已经很详尽了 数据很水 或许其他做法也能过 甚至有的错误代码也能过......

Code

#include <iostream>
using namespace std;
int n1,n2,n3,ans1,ans3,ans2;
int num;
char a[52],b[52],c[52];
int main()
{
	cin>>n1;
	for(int i=1;i<=n1;i++)
		cin>>a[i];
	cin>>n2;
	for(int i=1;i<=n2;i++)
		cin>>b[i];
	cin>>n3;
	for(int i=1;i<=n3;i++)
		cin>>c[i];
		
	for(int i=1;i<=min(n1,n2);i++)
		if(a[i]==b[i])
			ans1++;
		else
			break; 
	for(int i=1;i<=min(n1,n3);i++)
		if(c[i]==a[i])
			ans2++;
		else
			break; 
	for(int i=1;i<=min(n2,n3);i++)
		if(b[i]==c[i])
			ans3++;
		else
			break; 
	
	if(ans1>=max(ans2,ans3))
	{
		num=(n1+n2-2*ans1);
		num+=(n3+ans1-ans2*2);
	}
	else if(ans2>=max(ans1,ans3))
	{
		num=(n1+n3-2*ans2);
		num+=(n2+ans2-ans3*2);
	}
	else
	{
		num=(n2+n3-2*ans3);
		num+=(n1+ans3-ans1*2);
	}
	
	cout<<num;
	return 0;
}

本题解法不单一，此处提供一个思路：

首先容易注意到，一个最优的方案中，所留下的字符串一定是其中一个原字符串的前缀（不然这个三个字符串都是后续添加字符得到的，不如不添加这些字符让操作数更小）。

于是可以枚举是哪个字符串的哪个前缀，可以贪心地得到将三个字符串变为它需要的最小操作次数。

作为一个送分题，数据范围设计较小，有正确的思路并实现之即可得到100分。

std中实现了一个时间复杂度O(n)的上述做法。