解いた問題のソースコードと解説など。


SRM 476 Div2 Hard SubAnagrams

問題

http://apps.topcoder.com/wiki/display/tc/SRM+476

YのあるsubstringのアナグラムがXになるとき文字列Xが文字列Yのsubanagramであるという。いくつかの文字列がvector stringで与えられる。これらの文字列を結合した文字列Sをn個に分割したい。ただしS1 + S2 + ... + Sn = SでSi はSi+1のsubanagramでなければならない。分割数nを最大化せよ。

やりかた

kusano_progさんの回答を参考にしました。

文字列Sの長さをLとしてO(L^3)のDPで間に合う。
dp[i][j] := (文字列S[0...j]をS[0...i - 1]とS[i...j]に分割する時の最大の分割数)でDP。S[t...i-1]がS[i...j]のsubnagramになるようなtにたいして

dp[i][j] = max(dp[i][j], dp[t][i-1] + 1);

がなりたつ。

ソースはkusano_progさんのほぼ丸パクリになってしまったのでそちらをご参照ください。

いつも添字でこんらんしてしまう。

Get up! 明日のSUPER ST@R!