動的計画法での鉄則として蟻本にも書かれてるものだが、
bool値のDPは同じ計算量より多くの情報を保持できるので、オーダーが落ちやすい!
しかし世の中にはいくつかこれ以上オーダーが落ちないものもある。落ちやすいは100%落ちるというわけではない。それらを解く際に有効なテクニックの一つとして、真偽値の定数倍高速化ではC++のbitsetを用いるというのがある。
bitsetの使い方
内部的にはlong long をいくつかつなげた形で取られている。よって、1桁1桁に対していくつか左にずらすなどの操作は内部的にはlong long 間の演算となり、およそ1/64倍の定数倍高速化となる。
bitsetを利用した定数倍高速化テクニック
例
長さN(1 <= N <= 2000)の数列(1 <= A_i <= 2000)の部分列のうち、X(1 <= X <= 2000 * 2000)になるものが存在するか?
次のように動的計画法で解くと考えつくだろう。
bool dp[i][j] := i項目まで見て、選んだ数字の和がjになれるかどうか
普通に計算すると、O(N^2max(A))かかり、TLEとなる。
しかし、真偽値の更新のためbitsetを利用すると、次のようにきれいに書ける。
しかし、真偽値の更新のためbitsetを利用すると、次のようにきれいに書ける。
#include<bitset>
......
//更新式は
// dp[i + 1][j] |= dp[i][j]
// dp[i + 1][j + A[i]] |= dp[i][j]
//更新式から、iのDPの次元は配列自身の使いまわしで問題ないとわかる。
std::bitset<2010 * 2010> dp;//<>にサイズを指定して宣言する。
//dp[0] = 1;//メリットの一つでもある、配列と同じ感覚で扱えるというのがある。
//初期化ではゼロうめされてる。
for(int i = 0; i < N; i++){
dp = dp | (dp << A[i]);
//添え字のdp[a]のaは、aが作れるか否かなので、現時点での0~MAXまでの作れるか否かがわかる。
//結局のところ、すべての現時点で作れてるものに対して、A[i]を足したら作れるものを考えるので
//現時点のdp配列をA[i]個だけシフトそのまま流用すればよい。
//作りたい数 |0 |1 |2 |3 |4 |5 ...
//現時点での状況 |1 |0 |0 |1 |0 |1 ...
//A[i]==2のとき
// |0 |0 |1 |0 |0 |1 ...
//が元の状況でA[i]==2を採用した時の作れるか否かの情報
//一度作れればtrueとなるので、
//もともとのdpのbit値に、A[i]分だけシフトしたbit配列との論理和を足せば更新ができる。
}
cout << (dp[X] ? "OK", "NG") << endl;