WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Industry"問題http://codeforces.com/contest/320/problem/E訳カリラとディムナは広大なジャングルに住む2頭のジャッカルだ。ある日彼らはお金を得るため、木の伐採工場に出向いた(?)。anの高さのあるn本の木を木って欲しいと頼んだ。彼らは店でチェーンソーを買った。チェーンソーを1回使うと木の高さを1だけ減らせる。そのたびにチェーンソーのエネルギーを再充電せねばならない。充電のコストは切り終わった(高さが0になった)木のidに関係している。切り終わった木の最大のidがi(この木は最初高さがaiあったもの)だとすると、充電のコストはbiとなる。1つも切り終わっている木が無ければ、チェーンソーを再充電することはできない。チェーンソーは最初は充電されている状態である。カリラとディムナが全ての木をきり終える時の最小のコストを出力せよ。a[i]の時、どの直線が一番最小になるの?という問題になります。基本的にはこんな形になります。jが大きくなればなるほど初期値は大きいですが、傾斜が緩やかになるかんじです。最小値は2つを見比べて(L2とL3)jが小さいほう(L2)の方が小さくなった時点で、最小値はL2で確定になります。最小の線が分かるため、線の状態を凸包に保つ事が重要となります。こんな線の状態で、3本目の線を追加する時に、L1,L2の交点よりL2,L3の交点が右(x座標が大きい)にあれば、凸包の状態を保つ事ができます。L2にも最小値をとるチャンスがまだあるよ!L2はまだ無駄な線じゃないよ!ってことです。L1,L2の交点よりL2,L3の交点が左(x座標が小さい)となると、凸包の状態を保つ事ができず、L2の線は無駄なばかりか間違った答えを生み出してしまいます。よって、こうゆう場合、L2の線を除いてあげることが必要となります。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。