冒泡ioa
冒泡ioa

[CF559C] Gerald and Giant Chess(动态规划)

题目链接

题解

先介绍一个东西:多重集(multiset)的全排列(这里是特殊情况,即选的元素个数不超过任意集合中元素个数的情况)
我们定义集合的集合为多重集,比如我有 a_11a_22 …… a_nn
那么写成多重集就是 \(\left\{\left\{a_1·1\right\},\left\{a_2·2\right\},\cdots,\left\{a_n·n\right\}\right\}\)
如果我们要从中取 k 个数(上面说了,k 不大于 a_i),那么有多少种方案呢?

具体证明请移步至维基百科,这里直接给出结论:

multiset

也就是 C_{n+k-1}^{n+1}

那么这题其实如果我们把每一行看成一个集合,元素个数就是列数-1(因为我们最终目标是走到右下角,而如果走到了右侧,再走到右下角的方案已经确定,随意等价于走到右侧),如果没有黑格子的话,我们要选的元素个数也是列数-1,答案就是 C_{H+W-2}^{H-1}

而如果有黑格子,我们可以统计出不合法的方案数减去即可。

所谓不合法,就是在路径上走到过黑格子,为了避免重复,我们设 f[i] 为只经过第 i 个黑格子的方案数,对于它的求法,可以把它当成右下角,求贡献,对于区域内的黑格子,根据乘法原理,它们产生的不合法的方案数为 f[j]\times C_{x_i-x_j+y_i-y_j}^{x_i-x_j} 即原点到他的方案数乘上以第 j 个黑格子为左上角,第 i 个黑格子为右下角的子矩阵的方案数。

具体实现时可以按照坐标排个序,减少枚举量,设右下角为第 n+1 个黑格子,方便计算答案,还有就是不要弄混横纵坐标。

代码

没有标签
首页      动态规划      [CF559C] Gerald and Giant Chess(动态规划)

发表评论

textsms
account_circle
email

冒泡ioa

[CF559C] Gerald and Giant Chess(动态规划)
题目链接 题解 先介绍一个东西:多重集(multiset)的全排列(这里是特殊情况,即选的元素个数不超过任意集合中元素个数的情况) 我们定义集合的集合为多重集,比如我有 $a_1$ 个 $1$ ,…
扫描二维码继续阅读
2019-05-06