程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1159-Palindrome（DP/LCS變形）

POJ 1159-Palindrome（DP/LCS變形）

編輯：C++入門知識

POJ 1159-Palindrome（DP/LCS變形）

Palindrome Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 53770 Accepted: 18570

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

題意：求一個字符串變成回文串至少要添加多少個字符（可以在任意位置添加）

思路：將串s逆轉得到s’ （注意strrev()會CE sad） ，然後求s和s'的最長公共子序列（LCS）  n-LCS即為答案。

很吃驚? 其實是這樣的：因為s和s’的最長公共子序列肯定是回文，所以剩下的長度只需要添加n-LCS個字符既可以滿足總體回文了。。想象成添加可能不好理解，可以這麼想，LCS部分的字符串已經是回文了，所以我們不需要管它了，然後就是把剩余的字符插空了，舉個例子,比如 Ab3bd 反轉後得 s’ db3bA 所以LCS=3 （b3b） 那麼剩余的兩個字符分別為 A和d 現在我們依次把他們插入原串s：因為A在最左邊，所以在最右邊插入一個A 得Ab3bdA 然後此時的在右邊數第二位，所以我們在左邊數第二位插入一個d 得 Adb3bdA  ok大功告成。。。

 至於求LCS。。蒟蒻只會o（n*n） 然後數組要開short才能過。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define maxn 360
#define pp pair
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n;
short dp[5005][5005]={0};
char s[5010],t[5010];
void solve()
{
	for(int i=0;i