問題概要 数列があって、一ペア交換したときの転倒数の最小値を求めよ 小課題1 aとbを交換するとき(aがもともと左、a>b)、aとbの間にある数について、aと同じなら1、bと同じなら1、a>x>bなら2だけ転倒数が減る。 任意のペアについて確かめると、O(N^2)回領域…

問題概要 N階のダンジョンがあって、各階で消費する体力とコスト1で回復できる体力が決まっていて、Hを超えない。体力を常に1以上に保ったまま最下層まで行くのにかかる最小コストを求めよ。 小課題1 愚直DPをすると解ける。階数、残り体力を頂点として、コ…