問題ページ 解法 dp[i] = (i文字目までを考え、i文字目を'1'にしたときのスコアの最大) としてDPする。dp[i] = (区間[0,i)に内包される区間で得られるスコア, 全部'0'で0以上にはなる) + (i文字目を'1'にしたことで得られるスコア) = max(0, max(dp[j], j

問題ページ 解法 花を削除するのではなく条件を満たしつつ追加していくと考える。高さが低い花から順番に挿入していくと考える。dp[i] = (高さがiの花を挿入したときの美しさの最大)としてDPをする。dp[i] = max(dp[j], j

問題ページ 解法 寿司がa[i]個乗っている皿がどこにあったとしても選ばれる確率に影響はない。したがってN要素の数列a[i]ではなくcnt[i]=(i個乗っている皿の数)と情報を持つことができる。 dfs(x, y, z) = (1個乗っている皿がx枚、2個乗っている皿がy枚、3個…