TopCoder SRM 299 Div1 Medium PalindromePartition

問題

文字列sが与えられる。
文字列を連続する部分文字列に分割し、それぞれ全てが回文になっているようにしたい。
文字列は最小でいくつに分割する必要があるか、求めよ。

制約条件

sはアルファベット大文字からなる
sの長さ≦2500

方針

動的計画法による。
dp[i]を、i文字までを回文にするのに必要な分割の数とすると、
dp[i]=min{dp[j]+1 | jはj文字目からi文字目が回文になるようなもの}
という漸化式が立ってDPできる。


j文字目からi文字目までが回文なにるかどうかは、
O(n)の時間をかけると全体の計算量がO(n^3)になってTLEするので、
rolling hashを使って判定した。


けれど良く考えたら回文に一文字ずつ左右に足しても回文かどうかを見ていけば良かった。
can[i][j]をi文字目からj文字目が回文かどうかを持っておいて、
左に一文字、右に一文字ずつ配列を拡張していくようなDPをする的な意味。

ソースコード

typedef unsigned long long ll;
int n, dp[2501];
ll h[2501], rh[2501], pw[2501];

bool ok(int l,int r){
	ll a=(h[r]-h[l])*pw[n-l];
	ll b=(rh[n-l]-rh[n-r])*pw[r];
	return a==b;
}
class PalindromePartition {
	public:
	int partition(vector <string> s) 
	{
		string t=accumulate(all(s),string());
		n=t.size();
		
		h[0]=0; rh[0]=0; pw[0]=1;
		rep(i,n){
			h[i+1]=h[i]+(t[i]-'A'+1)*pw[i];
			rh[i+1]=rh[i]+(t[n-i-1]-'A'+1)*pw[i];
			pw[i+1]=pw[i]*29;
		}
		
		rep(i,n+1)dp[i]=inf;
		dp[0]=0;
		rep(i,n+1)rep(j,i)if(ok(j,i))dp[i]=min(dp[i],dp[j]+1);
		return dp[n];
	}
};