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

￡神魔★判官ぃ 2022-08-21 10:59 77阅读 0赞

# 回文 #

问题描述

回文是对称的串，也就是一个字串相同读取从左到右以及从右到左。你是写一个程序，给定的字符串，确定要被插入以获得回文字符串的字符的最小数目。作为一个例子，通过将2个字符，字符串“Ab3bd”可转化为一个回文（“dAb3bAd”或“Adb3bdA”）。然而，插入少于2个字符不产生回文。

输入

你的程序是从标准输入读取。第一行包含一个整数：输入字符串n的长度，3 <= N <= 5000。第二行包含一个字符串，长度为N的字符串是从“A”到“Z”大写字母组成，小写从“A”到“Z”和数字从“0”到“9”的信件。大写和小写字母被认为是不同的。

产量

你的程序写入到标准输出。第一行包含一个整数，它是所需的最小数量。

样本输入

5
    Ab3bd

样本输出

2
      
       
      
       
        
       题意：
    就是填多少字符使之变成回文字符串；
      
       
      
       
        
       #include<iostream>
    #include<cstring>
    #include<queue>
    #include<cstdio>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char a[5005],b[5005];
    int DP[2][5005];//因为求最长公共子序列只需要两行。
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            getchar();
            int i,j;
            gets(a);
            for(i=n-1;i>=0;i--)
                b[n-1-i]=a[i];
            //printf("%s\n",b);
            memset(DP,0,sizeof(DP));
            for(i=1;i<=n;i++)
            {
                 for(j=1;j<=n;j++)
                 {
                     if(a[i-1]==b[j-1])
                        DP[i%2][j]=DP[(i-1)%2][j-1]+1;
                     else
                        DP[i%2][j]=max(DP[(i-1)%2][j],DP[i%2][j-1]);
                 }
            }
            printf("%d\n",n-max(DP[1][n],DP[0][n]));//这地方看明白。
        }
        return 0;
    }