自动搬运

查看原文

来自洛谷，原作者为

	SilverLi Can you let me have some fun this time

搬运于2025-08-24 22:40:58，当前版本为作者最后更新于2023-04-21 22:27:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

密码脱落 の 传送门

题目中要求我们去找脱落的种子，首先我们知道。

种子在脱了几个不知道，种子脱在哪里也不知道。

这两个问题我们不能解决。

但可以反着想，是否可以去找没有脱落的种子，即找相同的。

那么又有一个问题：相同怎么找。

根据回文串的特性（左边和右边对称），

就有两种办法。

第一种

找到对称轴，左边和右边对比。

种子脱落之后，对称轴的位置也变得不好确定。

所以选择另一种方法。

第二种

把原串倒过来构造另一个串，去找两串中相同的子串。

设原串为 $s1$，倒序串为 $s2$。

定义 $f_{i,j}$ 表示 $s1$ 中前 $i$ 个种子与 $s2$ 中前 $j$ 个种子相同种子数。

则当 $s1_i=s2_j$ 时，表示找到一个相等的种子就让 $f_{i,j}=f_{i-1,j-1}+1$，而 $s1_i\ne s2_j$ 时 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1})$。

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int f[N][N];
string s1,s2;
int main() {
	cin>>s1;	s2=s1;
	int l=s1.size();
	reverse(s2.begin(),s2.end());		//翻转串
	for(int i=1;i<=l;++i)			
		for(int j=1;j<=l;++j)
			if(s1[i-1]==s2[j-1])	f[i][j]=f[i-1][j-1]+1;
			else	f[i][j]=max(f[i][j-1],f[i-1][j]);
	cout<<l-f[l][l];
	return 0;
}