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":"+"); }