专栏文章

题解：CF2066D1 Club of Young Aircraft Builders (easy version)

CCReatiQ
CF2066D1题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq91exk
此快照首次捕获于
2025/12/04 00:56
3 个月前
此快照最后确认于
2025/12/04 00:56
3 个月前
查看原文

组合意义

首先，顶层必须扔 cc 只飞机。
对于下面的每一层，需要决定它们看到的前 cc 只飞机分别是自己丢出去的还是楼上丢下来的。
而楼下总共丢出 m−cm-c 只飞机。
故答案为 ((n−1)cm−c)\large \binom{(n-1) c}{m-c}。

dp

记 dpi,jdp_{i,j} 为 n=i,m=jn=i,m=j 时原问题的答案，有：
dpi,j=∑0≤k≤c(ck)dpi−1,j−kdp_{i,j}=\sum_{0 \leq k \leq c} \binom{c}{k} dp_{i-1,j-k}
时间复杂度为 O(n⋅c⋅m)\mathcal{O}(n \cdot c \cdot m)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...