nyoj 37 回文字符串（LCS）

叁歲伎倆 2024-02-17 19:35 21阅读 0赞

### 回文字符串 ###

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 4

描述

所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。

输入

第一行给出整数N（0<N<100）  
接下来的N行，每行一个字符串，每个字符串长度不超过1000.

输出

每行输出所需添加的最少字符数

样例输入

1
    Ab3bd

样例输出

2

分析：将原字符串倒置，得到一个新的字符串，求两个字符串的最大公共子序列dp，用总长len-dp就是所需添加的最少字符数。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1000+10;
    char s1[maxn],s2[maxn];
    int dp[maxn][maxn];
    int main(){
    	int N;
    	scanf("%d",&N);
    	while(N--){
    		scanf("%s",s1);
    		int len=strlen(s1);
    		for(int i=len;i>=1;i--)
    		s2[len-i]=s1[i-1];
    		
    		memset(dp,0,sizeof(dp));
    		for(int i=1;i<=len;i++){
    			for(int j=1;j<=len;j++)
    			if(s1[i-1]==s2[j-1])
    			  dp[i][j]=dp[i-1][j-1]+1;
    			else 
    			  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    		}
    		
    		printf("%d\n",len-dp[len][len]);
    
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 37 回文字符串（LCS）

回文字符串时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如

叁歲伎倆/ 2024年02月17日 19:35/ 0 赞/ 22 阅读

相关回文字符串

public class HuiWenTest3 \{ /\\ \ @SERLIN \/ public static void main(String\[\]

分手后的思念是犯贱/ 2023年08月17日 17:14/ 0 赞/ 127 阅读

相关回文字符串

最近遇到两个题目，比较有意思，由于两个题目的描述比较相似，在这里就一起说了，做一个比较题目一：给定一个字符串，给该字符串添加一些字符，使其成为一个回文串，求需要添加的最少字

清疚/ 2023年06月02日 09:09/ 0 赞/ 5 阅读

相关 NYOJ 37 回文字符串

回文字符串时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如

Bertha 。/ 2022年08月25日 05:20/ 0 赞/ 133 阅读

相关 NYOJ 781 又见回文数

又见回文数时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述冷淡的回文数被水了，各种被水，然后他很生气，然后... 一个数从左边读

待我称王封你为后i/ 2022年08月25日 01:42/ 0 赞/ 152 阅读

相关 NYOJ 766 回文数

回文数时间限制： 1000 ms | 内存限制： 65535 KB 难度： 0 描述请寻找并输出1至1000000之间的数m，它满足m、m^2和m^3均为回文数

约定不等于承诺〃/ 2022年08月24日 14:29/ 0 赞/ 5 阅读

相关回文字符串

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。例如：abbc 添加2个字符可以变为

我就是我/ 2022年06月11日 04:25/ 0 赞/ 314 阅读

相关 NYOJ——1023—还是回文

还是回文时间限制：2000 ms | 内存限制：65535 KB 难度：3 描述判断回文串很简单，把字符串变成回文串也不难。现在我们增加点难度，给出一串字符

谁践踏了优雅/ 2022年05月18日 09:44/ 0 赞/ 133 阅读

相关 NYOJ 37 回文字符串——————水

回文字符串时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如

绝地灬酷狼/ 2022年05月09日 12:12/ 0 赞/ 137 阅读

相关验证回文字符串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

男娘i/ 2021年06月10日 20:38/ 0 赞/ 445 阅读