DP Q
二つの数列が与えられて、片方の数列の単調増加列になるような部分列すべての中で、もう一つの数列で与えられたスコアの合計が最大になるものを選ぶ問題
サンプルの小さい問題に関してはこれで解ける
このmaxの部分が素朴にO(N)だと全体でN^2になって、10^10だから間に合わない
そこでlog Nでmaxを計算できるアルゴリズムを使う
pythondef solve(N, HS, VS):
values = [0] * (N + 1)
for i in range(N):
h = HS[i]
values[h] = max(values[:h]) + VS[i]
return max(values)フェニック木
pythondef solve(N, HS, VS):
bit = [0] * (N + 1) # 1-origin
def bit_put(pos, val):
assert pos > 0
x = pos
while x <= N:
bit[x] = max(bit[x], val)
x += x & -x # (x & -x) = rightmost 1 = block width
def bit_max(pos):
assert pos > 0
ret = 0
x = pos
while x > 0:
ret = max(ret, bit[x])
x -= x & -x
return ret
for i in range(N):
h = HS[i]
m = bit_max(h)
bit_put(h, m + VS[i])
return bit_max(N)Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]