Indeedなう（本選B） : C - Palindrome Concatenation

なんで問題名が英語なんだろうね。
http://indeednow-finalb-open.contest.atcoder.jp/tasks/indeednow_2015_finalb_c

問題

N文字の文字列Sが与えられる。
これを幾つかの回文を連結した形に分割したい。

i文字の回文を１つ用いるとC[i]のコストがかかる。
Sを分割するための総コスト最小値を求めよ。

解法

x文字目までを分割するコストをcost[x]とすると、部分文字列S[y..x]が回文の時、cost[x]=min(cost[x], cost[y-1]+C[x-y+1])という単純なDPに落とし込める。
問題は部分文字列S[y..x]を高速に判定する方法である。

これは割と単純で、S[y]==S[x]かつ部分文字列S[(y+1)..(x-1)]が回文ならS[y..x]も回文と判定できる。
部分文字列を短い順から判定していけばO(N^2)で判定可能。
回文判定もコストのDPもO(N^2)。

int N;
string S;
int C[5050];
int isp[5050][5050];

ll co[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) cin>>C[i+1];
	
	for(l=1;l<=N;l++) {
		for(x=0;x+l-1<N;x++) {
			isp[x][l]=S[x]==S[x+(l-1)];
			if(l>=3) isp[x][l] &= isp[x+1][l-2];
		}
	}
	for(x=1;x<=N;x++) {
		co[x]=1<<30;
		for(l=1;l<=x;l++) if(isp[x-l][l]) co[x]=min(co[x],co[x-l]+C[l]);
	}
	cout<<co[N]<<endl;
}

まとめ

対称性を求めるとき、１つ小さな形の結果を用いて速く行うテクはしばしば出番があるね。