8月に入ったら情報オリンピックの過去問を解いてく予定なので動的計画法が使えないとどうにもならないと思い、勉強します。題材は蟻本の01ナップサック問題から ナップサック問題 重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品…

問題 Dragon Fantasy 解法 全探索＋枝刈り。BFSでときました。枝刈りをするときはループに入らせる前に走査して枝刈りさせないと無駄な探索が入り込んだりすることを知った。 心臓に悪いコード int n; int hx, hy, dx, dy, cx[21], cy[21]; double dist(doub…

問題 Princess's Marriage 解法 距離と期待値を期待値の降順でソートしてどれだけ護衛を雇えるか計算する 心臓に悪いコード int N, M; bool cmp(const pi &a, const pi &b){ return a.S > b.S; } int main(){ int D, P; while(scanf("%d%d", &N, &M) && N+M)…