蓝桥杯2016年第七届真题-密码脱落

解题思路:将字符串与反转后的字符串跑一遍最长公共子序列就可以的出最长回文串的长度,减去字符串的长度就可以的出脱落的个数

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main()
{
	char a[1005],b[1005];
	scanf("%s",a+1);
	int len;
	len=strlen(a+1);
	for(int i=1;i<=len;i++)
	{
		b[i]=a[len-i+1];
		//cout<<b[i];
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=len;i++)
	{
		for(int j=1;j<=len;j++)
		{
			if(a[i]==b[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout<<len-dp[len][len];
	return 0;
}