题目HDU 1513 K - Palindrome

女爷i 2022-09-25 11:28 87阅读 0赞

![20160821222622896][]

此题解题思路就是 ：求 原字符串 和它的 逆序字符串 的 最长公共子序列

用常规的动态规划，就可以求解，但是会空间超限，

所以就要想办法缩小数组，由于打表的时候只用到了上一行的数据，

课本上介绍说用一个a\[2\]\[\*\]的数组存就可以了，但是我有点不明白，就像是a和b交换，用一个中间值temp会容易的多

所以我就想为什么不用a\[3\]\[\*\]来保存呢，加上最近学会了使用取余是数组循环起来，就很容易解决了

最后一点要特别注意的地方就是：输出哪里最后的得到的一组数据必须是：

printf("%d\\n", n\-a\[n%3\]\[n\]);原因其实也很容易理解

已AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[3][5000];
    
    int main()
    {
        int n;
        char s[5005], r[5005];
        while((scanf("%d", &n))!=EOF)
        {
            scanf("%s", s);
            memset(a, 0, sizeof(a));
                for(int i=0; i<n; i++)
                    r[i] = s[n-i-1];
                for(int i=1; i<=n; i++)
                {
                    for(int j=0; j<=n; j++)
                    {
                        if(r[j-1]==s[i-1])
                            a[i%3][j] = a[(i-1)%3][j-1]+1;
                        else
                            a[i%3][j] = max(a[(i-1)%3][j], a[i%3][j-1]);
                    }
                }
                printf("%d\n", n-a[n%3][n]);
    
        }
        return 0;
    }

[20160821222622896]: /images/20220718/5bde6ddfd0924b08a8b640a7a50ceff1.png

发表评论取消回复

表情：

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

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

相关阅读

相关 hdu6599 I Love Palindrome String

由样例可知，题目中求的回文串数量，其实是本质不同的回文串数量，这个可以直接用回文树来做。考虑前半段是回文串这个限制，这个东西回文树不好做，可以再套一个马拉车，然后记录一下插

深藏阁楼爱情的钟/ 2023年06月03日 02:53/ 0 赞/ 9 阅读

相关题目HDU 1513 K - Palindrome

![20160821222622896][] 此题解题思路就是：求原字符串和它的逆序字符串的最长公共子序列用常规的动态规划，就可以求解，但是会空间超限，所

女爷i/ 2022年09月25日 11:28/ 0 赞/ 88 阅读

相关【杭电oj1513】Palindrome

Palindrome Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

爱被打了一巴掌/ 2022年09月25日 04:27/ 0 赞/ 186 阅读

相关算法题目——电梯(HDU-1008)

题目链接：[HDU-1008][] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q

柔情只为你懂/ 2022年09月10日 15:25/ 0 赞/ 186 阅读

相关 hdu1513Palindrome（动态规划之最长公共子序列变形+滚动数组）

回文问题描述回文是对称的串，也就是一个字串相同读取从左到右以及从右到左。你是写一个程序，给定的字符串，确定要被插入以获得回文字符串的字符的最小数目。

￡神魔★判官ぃ/ 2022年08月21日 10:59/ 0 赞/ 71 阅读

相关 hdu 题目分类比较详细

1001 这个就不用说了吧 1002 简单的大数 1003 DP经典问题，最大连续子段和 1004 简单

清疚/ 2022年08月10日 16:49/ 0 赞/ 172 阅读

相关杭电-1513Palindrome（LCS+滚动数组）

Palindrome Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

拼搏现实的明天。/ 2022年08月10日 05:46/ 0 赞/ 146 阅读

相关 hdu 题目分类

基础题：1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、 1032、1037、1040、1

电玩女神/ 2022年06月15日 22:21/ 0 赞/ 189 阅读

相关 HDU-6156 Palindrome Function(找规律)

Palindrome Function As we all know,a palindrome number is

我会带着你远行/ 2022年06月10日 13:23/ 0 赞/ 146 阅读

相关 HDU2029 Palindromes _easy version回文串

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java

﹏ヽ暗。殇╰゛Y/ 2022年05月11日 10:24/ 0 赞/ 186 阅读