PKU 1159-Palindrome

問題概要

ある文章を元に何文字か加えて回文を作りたい。加える文字数の最小値を求めよ

解法

文字数から最長回文部分列の文字数を引けば良い

実装(C++)

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int N;
char in[5001],rev[5001];
short dp[5001][5001];
int main() {
	N=atoi(gets(in));
	gets(in);

	for(int i=0;i<N;i++){
		rev[i]=in[N-1-i];
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(in[i-1]==rev[j-1]){
				dp[i][j]=max<short>(dp[i-1][j-1]+1,dp[i][j]);
			}
		}
	}
	printf("%d\n",N-dp[N][N]);
	return 0;
}