[IOI2000]回文字串

Posted on | In

今天模拟赛三道动态规划，这是最简单的一道

考试的时候想的是贪心，大力分类讨论一波以为能过

考完才知道正解就是一道最长公共子序列？？？

这个跟回文串的性质有关，它正着读和倒着读是完全一样的

这样的话我们就可以把原串反过来跟它自己匹配

最后的答案就是原串的长度减去匹配的长度

考完才发现我不会打最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
char s1[10086];
char s2[10086];
int f[5005][5005];
int n,ans;
int main()
{
    scanf("%s",s1+1);n=strlen(s1+1);
    for(register int i=1;i<=n;++i) s2[n-i+1]=s1[i];
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=n;++j)
            if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
    ans=n-f[n][n];
    printf("%d\n",ans);
    return 0;
}