P7967 [COCI2021-2022#2] Magneti 题解
Lazy_Labs
·
·
题解
前言
这篇题解是对 @zlttql 的巨佬思路的补充
分析
首先我们知道如果 r_i< r_j 那么如果 r_j 这一个约束条件满足了则 r_i 则不需要满足。
那么我们可以从小到大排序，每次插入一个磁铁。
DP 状态
这里我们需要解释一下“联通块”的意义：
“连通块”指几个磁铁通过“制约”连成的联通块，且“连通块”的两端没有“制约”（因为是按照从小到大插入的，所以两端的只需要满足大的能插进来就行了）
上图片：（黑色代表磁铁，红色代表磁铁的范围，橙色代表连通块）
此时 $r_1=2$ 即能吸引半径 $1$ 以内的磁铁，但是联通块只有黑色的那一块
此时加入一个 $r_2=3$ 即能吸引半径 $2$ 以内的磁铁的磁铁，并且使它们形成“连通块”。因为要连成“连通块”，那么就必须“挨在一起”，如下图。
则因为第 $2$ 块磁铁加入满足制约那么第 $1$ 块磁铁就一定满足，所以没必要记第一块磁铁的“制约”。即“连通块”只需要满足最左和最右不会被“吸引”即可。
DP 状态如楼上。
我们有三个转移：
第 $i$ 个磁铁单独成为了一个新组： $f_{i,j,k} \to f_{i-1,j-1,k-1}
第 i 个磁铁接在第 j 个组的端点： f_{i,j,k} \to f_{i,j,k} + f_{i-1,j,k-r_i} \times j \times 2 (k \ge r_i)
第 i 个磁铁把两个“连通块”接了起来：f_{i,j,k} \to f_{i,j,k} + f_{i-1,j+1,k-2 \times r_i+1} \times j \times (j+1) (k \ge 2\times r_i+1)
至于那两个接起来其实无所谓，只需要记下 i,j,k 的个数有多少即可。
最后运用插板法知答案为 \sum^l_{i=1}f_{n,1,i} \times \binom{l-i+n}{n}。