なんか久々なせいか計算量解析がガバガバだったのでメモ。

問題概要

正整数$M,K$と長さ$N$の数列$A, B$が与えられます。$(1, 2, \cdots, N)$の連続するとは限らない部分列$P=(P_1, P_2, \cdots, P_{|P|})$であって、以下の条件を満たす物のうち$\sum_{i=1}^{||P|} A_{P_i}$の最大値を求めてください。

• $\sum_{i=1}^{||P|} B_{P_i} \leq M$

問題リンク

解法

どう見てもDPなのでDPテーブルを考える。$M$が最大で200と小さいので、そこまでのBの和を持っておくのが自然。$\text{dp}_{i,j} :=$ 条件を満たす列であって最後に$i$を使い、$B$の和が$$であるような列のうちの和としてあり得る最大値、とするDPをすればよい。

空間は$O(NM)$。遷移は、$dp_{i,j}$へと遷移可能なのは$k=1,2,\cdots,K$についての通りしか無いのでで良い。全体でで、余裕を持って通る。

提出(Rust, 7ms)

use library::utils::{chlibs::ChLibs, input::Input, iterlibs::collect::CollectIter};

fn solve(ip: &mut Input) 

自省用にアホのメモをペタリ