程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1159-Palindrome(dp_回文串+滾動數組)

POJ 1159-Palindrome(dp_回文串+滾動數組)

編輯:C++入門知識

POJ 1159-Palindrome(dp_回文串+滾動數組)


Palindrome Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status

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

題意:讓你在原串裡面添加最少的字母個數使原串變成回文串。

思路:最少補充的字母個數=原序列的長度-原串和逆串的最長公共子串的長度。dp儲存的是從i到j的相同字母的個數。

PS:因為5000*5000肯定超內存,所以在這裡引入滾動數組的知識。滾動數組很適合用在二維DP而且是數組在很大時,可以節省內存,消除超內存的隱患!

滾動數組講解

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int inf=0x3f3f3f3f;

char str1[5010];
char str2[5010];
int dp[2][5010];
int main()
{
    int n,i,j;
    while(~scanf("%d",&n)){
        getchar();
        for(i=1;i<=n;i++){
            scanf("%c",&str1[i]);
            str2[n-i+1]=str1[i];
        }
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            if(str1[i]==str2[j])
                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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved