DP Q

二つの数列が与えられて、片方の数列の単調増加列になるような部分列すべての中で、もう一つの数列で与えられたスコアの合計が最大になるものを選ぶ問題

サンプルの小さい問題に関してはこれで解ける

このmaxの部分が素朴にO(N)だと全体でN^2になって、10^10だから間に合わない

そこでlog Nでmaxを計算できるアルゴリズムを使う

code:python

def solve(N, HS, VS):

for i in range(N):

return max(values)

フェニック木

code:python

def solve(N, HS, VS):

def bit_put(pos, val):

assert pos > 0

x = pos

while x <= N:

x += x & -x # (x & -x) = rightmost 1 = block width

def bit_max(pos):

assert pos > 0

ret = 0

x = pos

while x > 0:

x -= x & -x

return ret

for i in range(N):

m = bit_max(h)

return bit_max(N)