Loading...
2026/02/09
なんか久々なせいか計算量解析がガバガバだったのでメモ。
正整数と長さの数列が与えられます。の連続するとは限らない部分列であって、以下の条件を満たす物のうちの最大値を求めてください。
どう見てもDPなのでDPテーブルを考える。が最大で200と小さいので、そこまでのBの和を持っておくのが自然。 条件を満たす列であって最後にを使い、の和がであるような列のうちの和としてあり得る最大値、とするDPをすればよい。
空間は。遷移は、へと遷移可能なのはについての通りしか無いのでで良い。全体でで、余裕を持って通る。
use library::utils::{chlibs::ChLibs, input::Input, iterlibs::collect::CollectIter}; fn solve(ip: &mut Input)
自省用にアホのメモをペタリ
