hdu-1513-Palindrome

Palindrome

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4052    Accepted Submission(s): 1377

Problem Description

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.

Input

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

Output

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

Sample Input

5 Ab3bd

Sample Output

2

Source

IOI 2000

题目分析：

意思就是让你在一个字符串中添几个字符让这个字符串成为回文串        这你要理解  lcs    如果明白了lcs是怎么查最长子序列的话就很好办了

比如说   123     321    用lcs 查一遍等于len=1              123321       这个串就是回文  但是我刚开始的思路就是把  123321  分成   123     321    两个串查他们的公共子串 然后总长度 6-2*len=4   但是这个串应该是0 的。然后我又看了看lcs     发现   abcsff      cbaiik    这个查出来是1     abcsff     iiabck   这个查出来就是  3    该是对lcs的理解就是错的我理解成有多少个相同字符就是多少呢！

那么知道了lcs 是怎么查的这个就好办了，只需把原串倒序一下  对这两个进行查找就行了，如果是回文串结果肯定是总长度了 如果不是回文那么查出的就是公共子串的长度那么    总长度减去公共长度及时需要添的了                                       比如 abcf  g cbah    倒置之后是    habc g fcba    红色部分和绿色部分只能查出有个长度为1的子串（上边已经说过lcs是怎么查的了）那么倒置后就相当于红色部分对红色部分查那么在纸上掩饰一边查找的结果应该是 5    abcg 一个长4 还有 cbah   对cbah  查出一个共5个  9-5=4   那么这个在添  4个就是回文了看看是不是

另外这个数据有点大需要用滚动数组   下边是看别人的滚动数组解析

相信很多同学都学过时间复杂度，在以前的很多程序编译里面我们也都看到过时间复杂度的优化，因为这个是一个很重要的因素，而且一般的ACM题目都是卡的时间，卡空间复杂度的不是很多，但是这里就卡了空间复杂度，这里我们介绍一种优化空间复杂度的方法——滚动数组。

下面首先介绍一下这个思想：滚动数组很适合用在二维ＤＰ而且是数组在很大时，可以节省内存，消除超内存的隐患！具体思想还是看了网上的资料，转载一个，共同享用吧！

滚动数组 举个简单的例子：

int i,d[100];

d[0]=1;d[1]=1;

for(i=2;i<100;i++)

d[i]=d[i-1]+d[i-2];

printf("%d",d[99]);

上面这个循环d[i]只需要解集中的前2个解d[i-1]和d[i-2];

为了节约空间用滚动数组的方法

int d[3];

d[0]=1;d[1]=1;

for(i=2;i<100;i++)

d[i%3]=d[(i-1)%3]+d[(i-2)%3];

printf("%d",d[99%3]);

注意上面的运算，我们只留了最近的3个解，数组好象在“滚动”一样，所以叫滚动数组

对于二维数组也可以用这种方法 例如：

int i,j,d[100][100];

for(i=1;i<100;i++)

   for(j=0;j<100;j++)

       d[i][j]=d[i-1][j]+d[i][j-1];

上?的d[i][j]忪便赖于d[i-1][j],d[i][j-1];

迿用滚动数组

int i,,j,d[2][100];

for(i=1;i<100;i++)

   for(j=0;j<100;j++)

       d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];

#include<cstdio>
#include<cstring>
#define max(a,b)  (a>b?a:b)
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    int dp[2][5010];
    char str1[5010],str2[5010];
    scanf("%s",str1);
      strcpy(str2,str1);  
        strrev(str2);  //  strrev( ) c里面的倒置函数 
        memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
       {
           if(str1[i-1]==str2[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-dp[n%2][n]);
  }
  return 0;
}