题解 P4370 [Code+#4]组合数问题2
某次钟神讲课后来补了这道题。
Description
简化题意：给定一个 \(n\)，要求选出 \(k\) 个组合数 \(C_a^b\)，是他们的和最大。其中 \(a,b\) 必须满足 \(0 \le a \le b \le n\) 。
Solution
先考虑如何找到最大的 \(k\) 个组合数。
我们知道组合数的递推式是 \(C_n^m = C_{n-1}^{m-1} + C_{n-1}^{m}\)，并且这个式子就是杨辉三角的形式。
尝试把前几行写出来。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
观察一下发现对于第 \(i\) 行，第 \(\frac{i}{2}\) 个数是最大的；对于每一列，越靠下越大。并且最大的是 \(C_n^{\frac{n}{2}}\)
那么考虑用广搜的思想，先把最大的 \(C_n^{\frac{n}{2}}\) 加进去，然后不断向周围三个方向扩展，取出前 \(k\) 大即可。
扩展的时候注意判断是否在界内。
注意判断该位置是否入队过，这里使用 map 标记判断。
但是我们忽视一个问题：我们并不能比较 \(C_{a}^{b}\) 的大小。因为我们求不出来，取模的话就会使得大小无法比较。如何解决？
根据钟神的思路想到高中的一个知识点：
\[\log (x \times y) = \log x + \log y \]\[\log (\frac{x}{y}) = \log x - \log y \]那么我们的 \(C_{a}^{b}\) 是不是也可以表示了？
设 \(Log_i = \sum_{j=1}^{i} \log j\)，有：
\[\log C_a^b = Log_a - Log_b - Log_{a-b} \]众所周知， \(f(x) = \log x\) 是单调递增函数，所以加入优队时比较 \(\log C_a^b\) 的大小就好了。
Code
/*
Work by: Suzt_ilymics
Problem: P4370 [Code+#4]组合数问题2
Knowledge: 优先队列，log部分知识
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#include