[AHOI2022] 山河重整 题解

标签：山河 题解 重整 ge AHOI2022 sim

T3，一个不错的数学题，给了不少的暴力分。

Statement

求有多少值域为 \([1,n]\) 的集合，01背包可以凑出 \(1\sim n\) 中的所有数字。

Subtask \(1\sim 6\)

我们从小到大选择每一个数，不难发现凑出来的数字一定是 \([1,n]\) 的一段前缀。
于是考虑 dp，记 \(f_{i,j}\) 表示选择完了前 \(i\) 个数，可以表示出 \([1,j]\) 中的所有数。
如何转移？考虑当前加 \(i + 1\)，新扩展的可凑区间为 \([i + 1, i + j + 1]\)。于是，如果要让这段区间造成贡献必须满足 \(j + 1 \ge i + 1 \implies j \ge i\)。
于是转移写成

\[f_{i+1,i+1+j}\gets f_{i,j}\quad if\ j \ge i \]

时间复杂度 \(\mathcal{O}(n^2)\)，足以通过 \(n\le 5000\)。

标签：山河,题解,重整,ge,AHOI2022,sim
From： https://www.cnblogs.com/misterrabbit/p/17077183.html