[蓝桥杯 2016 省 A] 密码脱落

· · 题解

密码脱落 の 传送门

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

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

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

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

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

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

就有两种办法。

第一种

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

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

所以选择另一种方法。

第二种

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

设原串为 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;
}