ABC237F |LIS| = 3
解説AC
公式解説で解法だけみて、実装は自力でしてみようと思ったのですが、これも上手くいきませんでした。結局、実装も解説のものを確認しました。
LISの長さが3未満の保持方法
未確定の部分はinf、今回ならM+1としておけばよいようです。
例えば、{2,5}というLISを持つ数列はdp[i][2][5][M+1]という感じになります。
dp遷移におけるループ
a1,a2,a3のループ部分は、単調増加にしたくなります。
イメージ
for a1 = 1 to M+1
for a2 = a1+1 to M+1
for a3 = a2+1 to M+1
しかし、このようにするとM+1を複数含む場合の遷移が起こらないため、だめでした。
そのため、ループ部分は、
for a1 = 1 to M+1
for a2 = 1 to M+1
for a3 = 1 to M+1
と、しておく必要があります。
dp[i][2][5][1] += dp[i-1][1][5][1]ような不正な更新が行われますが、これらは全て0になっているので問題ないということでした。
