回文

SRM 708 DIV1 Medium: PalindromicSubseq

文字列回文 DP 数え上げ

X[i]の値を具体的に求めていこう。各文字S[i]についてそれぞれX[i]を求める。S[i]がある回文に含まれる場合、S[i]と一致するようなもじS[j]がある。ただし、i=jでS[i=j]が奇数長回文の中心である場合も含む。iとjを総当りで固定した場合、それだけでO(N^2)…