JOI難易度8
JOI
JOI本選
JOI難易度8
DP
DP値を利用して状態復元
Dijkstra法
最短路問題
燃料補給系問題
グラフ問題
AtCoder
AOJ
最適解の形を考える
解を変形していく(最適性を失わずに)
固定する変数を入れ替えて考える
ある量を固定して考える
今が良いほど未来も良いGreedy
Greedy
ある量を決めるとGreedy
dp の値そのものを用いて現在状態を復元する系の問題。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 個の木 があって、それぞれ高さは である。 フクロモモンガは最初は、木 1 の高さ の地点にいる。フクロモモンガは木を飛び移り…
これはアレだ!!! DP の最適値そのものの値を利用して次の遷移を作る系。フクロモモンガなんかもそういう系の問題だった覚えがある。 問題へのリンク 問題概要 2 つの町 (1 と 2) がある。 個のイベントがあって、それぞれ町 において発生し、時刻 に始ま…
スライド最小値の練習 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテム…