かっつのメモ帳

主に競プロ 時々日記

Slope Trick

Codeforces Round #371 (Div. 1) C-Sonya and Problem Wihtout a Legend

問題のリンク 問題概要 長さ $N$ の数列 $ A _ {i} $ が与えられる。数列の値を $1$ 変更するのにコスト $1$ がかかる。この数列を狭義単調増加列にするのに必要な最小コストを求めよ。 制約 $1 \leq N \leq 3000$ $1 \leq A _ {i} \leq 10^{9}$ 解法 CFブロ…