傾き最適化DP：Luogu P2365とSDOI2012タスクスケジューリング問題の解法
問題文
動的計画法の問題を考察します。便宜上、問題文中の費用係数を\\(v_i\\)で表現します。
\\(f_i\\)を第\\(i\\�\\)位置までの最適解と定義します。各遷移は、\\(i\\)番目に区間\\([j+1,i]\\)のコストを追加する操作です。
明らかに、累和を用いて最適化できます。しかし\\(s\\)の存在により、直接次元を追加してグループ数を記録すると大きなオーバーヘッドが発生し ...
6月17日 17:27 投稿