この解説でも、…
を#
と表記します。
まず、次のようなDPをすることを考えます。
・ 番目の.
までを見て、.
を 個ストック(部分列を取る時に消えていないこと)していて、現在ストックしている.
を全て取り払ったときに最も右の#
の区間の長さが であるような、操作と取った部分列の組の個数
まず、このDPは の場合を考える必要はありません。
このDPの遷移を列挙していきます。
・ 今見ている.
をストックする場合
・ 今見ている.
をストックせず、ストックがある場合 ただし、 (今ストックしている.
を消すことができず、#
が孤立してしまうため)
・ 今見ている.
をストックせず、ストックがない場合
・ 今見ている.
とストックしている.
を使って#
を作り、ストックが完全に消え、その#
を部分列を取る時に消す場合
・ 今見ている.
とストックしている.
を使って#
を作り、ストックが残り、その#
を部分列を取る時に消す場合 ただし、
・ 今見ている.
とストックしている.
を使って#
を作り、ストックが残り、その#
を部分列を取る時に消さない場合 ただし、
・ 今見ている.
とストックしている.
を使って#
を作り、ストックが完全に消え、その#
を部分列を取る時に消さない場合
ここで、になった場合、どのような遷移をしてもストックが残る遷移に関わってから になるため、この状態をまとめることができます。そのため、それぞれの ごとに状態数を に抑えることができます。これを行列累乗で計算することで、計算量がとなり、ACすることができました。