CODE FESTIVAL 2014 Hardが開始されました。
CODE FESTIVAL 2014 Hardは終了しました。
\({\rm DP}[i][j]: \) \(i\) 番目まで見て \(i\) 番目の座標が \(p_i+j\) 以下である位置の選び方の総数 という\({\rm DP}\) を考えます。 これは尺取り法を用いると各 \(i\) について \(O(\max l)\) で更新できるので、全体で \(O(n \max l)\) で解くことができます。
投稿日時: 最終更新: