POJ(PKU) 1159 Palindrome

• 問題概要

文字数N(<=5000)とN文字の文字列が与えられる。
与えられた文字列を回文にするには最小何文字新たに挿入すればよいか。

• 解法

N <= 5000 より、オーダーはO(N^2)くらいかなと考える。

まず、左から読んだときの文字列と右から読んだときの文字列について最長共通部分列を求める。
真ん中になる文字を決め、その文字から右の文字列と左の文字列に共通する文字の数を先ほど求めた共通部分列から求めて、必要な文字数の最小値をprintf.

日本語が分かりにくくてごめんなさい。
もっといい解法がある気がする。
intで配列とったらMLEになったのでshort intにした。

#include <cstdio>
#include <algorithm>
#include <cstdio>

using namespace std;

short int dp[5003][5003]={0};

int main(){
  
 short int n,ans = 10000;
  char s[5003];
  
  scanf("%d%s",&n,&s);
  
  for(int i = 1;i <= n;i++){
    for(int j = 1;j <= n;j++){
      int h = n - j + 1;
      if(i + j > n)continue;
      if(s[i-1] == s[h-1]){
	short int y = dp[i-1][j-1] + 1;
	dp[i][j] = max(dp[i][j],y);
      }else{
	dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
      }
    }
  }
  
  for(short int i = 1;i <= n;i++){
    short int q = i;
    while(q < n){
      if(s[i-1] == s[q]){
	q++;
      }else{
	break;
      }
    }
    short int tmp = n - 1 - dp[i-1][n-q]*2+i-q;
    ans = min(ans,tmp);
  }
  printf("%d\n",ans);
  
  return 0;
}