Codeforces 137 D. Palindromes

問題

文字列が与えられる。
これをk個以下に分割して、それぞれが回文になっているようにしたい。
回文にするために変更するアルファベットの個数の最小値を求め、回文を具体的に一通り+で区切って出力せよ。

制約条件

k≦500
文字列の長さ≦500

方針

動的計画法による。
dp[i][j]を、j文字目までをi分割して、それぞれが回文になっているときの最小のコストとする。
すると、dp[i][j]=min{dp[i-1][k]+cost(k,j)}の漸化式が成り立つ。
ただしここでcost(k,j)はk文字目からj文字目までを回文にするのにかかるコスト。


これを更新するようなDPをすればよい。
costの部分は一回ごとにO(n^2)かかるが、メモ化あるいは前計算により、O(n^2)で全部計算することができる。
よって全体の計算量はO(n^3)となる。


経路復元もする。

ソースコード

int n,k;
int dp[501][501],prev[501][501];
string in;
int memo[501][501];
int cost(int l,int r){
	if(memo[l][r]>=0)return memo[l][r];
	int &res=memo[l][r];
	res=0;
	for(int i=l,j=r-1;i<j;i++,j--)if(in[i]!=in[j])res++;
	return res;
}

void run()
{
	cin>>in>>k;
	n=in.size();
	rep(i,k+1)rep(j,n+1)dp[i][j]=inf;
	dp[0][0]=0;
	memset(memo,-1,sizeof(memo));
	rep(i,k)rep(j,n+1){
		rep(l,j)if(dp[i+1][j]>dp[i][l]+cost(l,j)){
			dp[i+1][j]=dp[i][l]+cost(l,j);
			prev[i+1][j]=l;
		}
	}
	int ans=inf,ansk;
	rep(i,k+1)if(ans>dp[i][n])ans=dp[i][n],ansk=i;
	cout<<ans<<endl;
	int p=n;
	vs v;
	rep(i,ansk){
		int pp=prev[ansk-i][p];
		string s=in.substr(pp,p-pp);
		rep(j,s.size()/2)if(s[j]!=s[s.size()-j-1])s[s.size()-j-1]=s[j];
		v.pb(s);
		p=pp;
	}
	reverse(all(v));
	rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":"+");
}