atcoder.jp 解法 香辛料の消費量は、整数以外も選択できるがどこかで調整すればすべて整数にすることができるので、最初から整数で考えてよい。 ナップザックDP感があるので、普通にDPするしようとすると、 dp[i][w] ← i番目までの料理を作った時、香辛料をw…

セグメント木 セグメント木は、区間更新・区間上の最小値や和などをO(logn)で求めることができるデータ構造です。 セグメント木を理解するために役立つリソース かつっぱさんの動画です。説明が丁寧なのでわかりやすいです。 part1では、セグメント木の雰囲…

AOJの問題 RMQ and RUQ、RSQ and RAQからそれぞれ関数をとってきて貼り付けただけでは解けない。 加算の際に多少工夫が必要。 RMQ and RUQでは、2分木に区間和を保持していたが、今回必要なのは区間の最小値なので、それを保持する。 加算の際には、区間の全…

AOJの問題 RSQ&RAQのコードを少し変更しただけ。 区間更新の場合は加算と違って、普通に値を代入するだけでよい。 遅延配列の要素は、更新クエリで与えられることのない値で初期化すること。これがフラグの代わりになる。 実装 #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

問題 RMQは、与えられた区間の最小値を求めるというもの。 セグメント木を使って解きます。 実装 セグメント木の実装の中で何をしているかはコメントに書いてあります。 AOJのテストケースはパスしましたが、バグが潜んでいるかもしれません。 #include <bits/stdc++.h> usi</bits/stdc++.h>…