問題 問題のURLはこちらです。 No.409 ダイエット - yukicoder 考えたこと 動的計画法を使います。配列を次のように定義します。 日目にドーナツを食べた時の体重の変化量の最小値すると、その時の漸化式は、 なお、最初の行を簡単に説明すると、 (日目にド…

直線集合L={f_i(x)=a_ix+b_i}に対して、「Lへの直線f_k(x)=a_k x+b_kの追加」(以下、追加クエリ)と、「あるxに対し、Lの中で最小値(あるいは最大値)を取るような直線の値を求める」(以下、最小値クエリ)という2つのクエリを効率的に行うことが出来ます。