問題文: https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day3.pdf
解法:
L=300000という時点で何となく「dp[i][j]:=(i文字目まで見たときに文字jで部分列が終了する部分列をつくる場合の数)」というO(26L)の解法が浮かび上がります。
ところで、i文字目の文字を使う際は規則に違反しないアルファベットからつなげればいいので、
dp[i][str[i]]=Σdp[i-1][(使ってもよい文字)]
という式が成立します。
i文字目の文字を使わない際,既に文字jで終わっているのでその際は
dp[i][j]=dp[i-1][j]となります。
そして,以上から最終的な答えはΣ[j=0_25]dp[L-1][j]です。
文字を使わないことを27番目の文字としてDPテーブルに組み込むと残りはただのDPです。
dp[27][300001]を組み込むとMLEが出たので,配列を再利用してdpテーブルを圧縮するとゴールです。
諸感想:手元にDPテーブルを書くとなんとなくわかってしまった
コード:
