問題リンク
100位切れたのはうれしいね
解説
見た目が区間dpと書いてあるので、まずは区間dpを定義します。
![dp[l][r] := [l, r)](https://chart.apis.google.com/chart?cht=tx&chl=%20dp%5Bl%5D%5Br%5D%20%3A%3D%20%5Bl%2C%20r%29)
にあるセグメントの数の最大値
そうすると右端をソートして(右端が同じ場合左端が右にあるものから)左から見ていきます。
そうすると、セグメントが
のとき、
において
![dp[i][r] \leftarrow \max(dp[i][r], dp[i][l] + dp[l][r] + 1)](https://chart.apis.google.com/chart?cht=tx&chl=%20dp%5Bi%5D%5Br%5D%20%5Cleftarrow%20%5Cmax%28dp%5Bi%5D%5Br%5D%2C%20dp%5Bi%5D%5Bl%5D%20%2B%20dp%5Bl%5D%5Br%5D%20%2B%201%29)
となります。
と
に関しては左端右端が被る分には問題がないことに注意しましょう。
あとは区間を取らない場合に注意すればこの問題は解けました。(区間が無駄に大きいので座圧しておきましょうね)
計算量は
です。
提出コード
codeforces.com
