题解 P1435 【回文字串】

2018-08-13 07:35:46来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折


蒟蒻的第一篇题解……

dalao勿喷……


题目传送门

我们知道,回文串就是正反读都一样(废话) 所以我们来分析一下一个样例:as3da

对于这一组样例,我们进行如下简(bao)便(li)操作:

as3da->as3daad3sa(接上一个反串)

这个串明显是一个回文串 为了保证这个串始终是一个回文串,我们删除掉这个串前后两个部分中所有 同样位置上相同的部分

步骤如下:

as3da ad3sa ->as3da ad3sa->sd da

我们不难看出,剩余部分是sd的回文串

在原串中,已经存在了串sd,所以我们只需加入ds

ads3sda

(其实就是找原串和反串的最长公共子序列)

上代码:

//此题dp的关键就是要想到最长公共子序列
#include <cstdio>
#include <iostream>
using namespace std;
int n,ans,f[5001][5001];//f[i][j]为s数组的前i个数与k数组前j个个数所组成的最长子序列 
char s[5001],k[5001];
int main()
{
    scanf("%d\n",&n);
    for(int i=1; i<=n; i++)s[i]=getchar(),k [n-i+1]=s[i];
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(s[i]==k[j])
            {//如果子序列还能继续 
                f[i][j]=f[i-1][j-1]+1;
            }
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    printf("%d",n-f[n][n]);
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:2019届网易游戏校招-测试开发工程师编程题-C++

下一篇:[是题解哦] 洛谷 P1342 请柬