51Nod 1092 回文字符串——————LCM

男娘i 2022-05-10 15:00 151阅读 0赞

## [1092 回文字符串][1092] ##

--------------------

基准时间限制：1 秒  
空间限制：131072 KB  
分值: 10  
难度：2级算法题

--------------------

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。  
例如：abbc 添加2个字符可以变为 acbbca，也可以添加3个变为 abbcbba。方案1只需要添加2个字符，是所有方案中添加字符数量最少的。

--------------------

#### Input ####

输入一个字符串Str，Str的长度 <= 1000。

#### Output ####

输出最少添加多少个字符可以使之变为回文字串。

#### Input示例 ####

abbc

#### Output示例 ####

2

--------------------

将原始字符串s1倒置得到s2  
求得s1,s2的最长公共子序列LCS(s1,s2)  
s1 的长度就是Len  
结果就是Len - LCS(s1,s2)

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e3+7;
    char s1[MAXN];
    char s2[MAXN];
    int  dp[MAXN][MAXN];
    int main()
    {
        
            memset(dp,0,sizeof(dp));
            scanf("%s",s1);
            int len=strlen(s1);
            for(int i=0;i<len;i++)
                    s2[len-1-i] = s1[i];
            for(int i=0;i<len;i++)
                    for(int j=0;j<len;j++)
                            if(s1[i]==s2[j])
                                    dp[i+1][j+1] = dp[i][j]+1;
                            else
                                    dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
    
             printf("%d\n",len-dp[len][len]);
    
            return 0;
    }

[1092]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1092

发表评论取消回复

表情：

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

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

相关阅读

相关 1092 回文字符串（最长公共子序列）

[1092 回文字符串][1092] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 10 [1092]: http://www.51

﹏ヽ暗。殇╰゛Y/ 2024年02月18日 14:26/ 0 赞/ 4 阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 215 阅读

相关 51nod 1092 回文字符串 dp问题

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

短命女/ 2022年08月20日 12:23/ 0 赞/ 18 阅读

相关 51nod 1154回文串划分 dp+递推

题意：有一个字符串S，求S最少可以被划分为多少个回文串。例如：abbaabaa，有多种划分方式。 a|bb|aabaa - 3 个回文串 a|bb|a|a

男娘i/ 2022年08月19日 15:18/ 0 赞/ 147 阅读

相关 51nod 1434 数论区间LCM问题

题意：一个整数序列S的LCM（最小公倍数）是指最小的正整数X使得它是序列S中所有元素的倍数，那么LCM(S)=X。例如，LCM(2)=2,LCM(4,6)=12,LCM

川长思鸟来/ 2022年08月19日 15:13/ 0 赞/ 235 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 225 阅读

相关 51nod-1770

为该问题添加一个话题隐藏话题 [1770 数数字][1770] 基准时间限制：1 秒空间限制：262144 KB 分值: 20 [难度：3级算法题][3] ![s

小灰灰/ 2022年05月28日 12:51/ 0 赞/ 196 阅读

相关 51nod--1284

[1284 2 3 5 7的倍数][1284_2_3_5_7] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][

分手后的思念是犯贱/ 2022年05月27日 11:22/ 0 赞/ 204 阅读

相关 51Nod 1092 回文字符串——————LCM

[1092 回文字符串][1092] -------------------- 基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级

男娘i/ 2022年05月10日 15:00/ 0 赞/ 152 阅读

相关 51Nod 1088 最长回文子串——————Manacher,马拉车算法

-------------------- [ 51Nod 1088 最长回文子串][51Nod 1088] 基准时间限制：1 秒空间限制：131072 KB

深藏阁楼爱情的钟/ 2022年05月10日 14:36/ 0 赞/ 223 阅读