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; }