B
好题。
这题其实是原题，在大工VS辽实的T3里出现过，基本是一摸一样。
对于观看这个题解呢，我的理解是把两个结合起来观看，分别是 这个和这个，结合起来看的话无论是从感官还是从方便理解来看都很舒服。
好了，接下来我们说一下这个题的思路。
你考虑，你在一段长度为\(m\)的区间里至少要选两个，最终要求结果最小，所以一段长度为\(m\)要选两个。
我们钦定状态\(dp_{i,j}\)表示最后选的汤圆的下标为\(i\)，倒数第二个选的是\(j\)
你考虑怎么转移这个东西，显然得到一段公式：
那么你考虑这玩意怎么做优化，因为这个做法显然是\(O(n^3)\)的。
你考虑，对于\(dp_{i,j}\)，他需要比较的是\(dp_{j,i-m+1}\to dp_{j,j-1}\)；对于\(dp_{i+1,j}\)，他需要比较的是\(dp_{j,i-m} \to dp_{j,j-1}\),欸，这个时候你会惊奇的发现，对于\(dp_{j,i-m+1} \to dp_{j,j-1}\)这一段，他的枚举是冗余的，这张图片会更好理解：
这就是优化的地方，你考虑，我记录一个\(res\)，表示当前上端区间的最小值，而这段区间的最小值，其实就是\(min(res,dp_{j,i-m})\),那么就可以把枚举\(k\)这个步骤给省略了！
这个时候再明确一下枚举顺序就可以了！
你考虑，在求这个位置的最小值的时候，需要跟他前面的进行比较，所以，\(j\)需要从小到大进行枚举：for(int j = 1;j <= n;j++)
但是你考虑，对于枚举最小值的时候，他跟\(01\)背包的过程是类似的，如果你正着枚举的话，你有可能会重复，而且这玩意是一个类似滑动窗口的东西，所以你要倒着扫。
记得初始化并且取模！直接就滚动数组就可以解决这个题了。
D
先给几个前置知识：
- 快速计算斐波那契数列的通项公式:$$\sum_{i=1}^{n}F_i = F_{n+2}-1$$
接下来我们给出证明。
首先明确一个东西----数学归纳法:当一个等式在\(m\)下成立，推导过后\(m+1\)也成立，则该等式成立(注意，前提是在\(1\)的情况下他也成立)
那么就好整了，当\(n = 1\)时这个式子显然是成立的，\(2-1 = 1\)，
那么引出有关\(m+1\)的等式：
\(\;\;\;\;\;\;\;\)由结论：
\[\sum_{i=1}^{n}F_i = F_{n+2}-1 \]\(\;\;\;\;\;\;\;\)得到:
\[\begin{aligned} \sum_{i=1}^{m+1} &= \sum_{i=1}^{m}F_i+F_{m+1} \\ &= F_{m+2}+F_{m+1}-1\\ &=F_{m+3}-1 \end{aligned} \]\(\;\;\;\;\;\;\)则该式子在\(m+1\)与\(1\)下均成立，故此式子成立。
- 有关小球与盒子的公式：
\(\;\;\;\;\;\;\)这个还是挺好理解的,前面那个是有\(n\)个不同小球放入\(m\)个不同盒子中，每个盒子可以为空。
\(\;\;\;\;\;\;\)后面那个\(S(n,i)\)就是斯特林数，他的意思就是从\(n\)个不同的小球放入\(m\)个相同的盒子，盒子不可以为空。那么意思就显然了
接下来我们把原来的式子推一下：
\[\begin{aligned} &\sum_{i=1}^{n}(\sum_{m=1}^{r}F_i)!\times i! \times \sum_{l=0}^{i}\sum_{j=0}^{\sum_{t=1}^{r}F_t} \frac{S(K,i-l)}{l!} \frac{S(i,\sum_{w=1}^{r}F_w-j)}{j!} \\ =&\sum_{i=1}^{n}L! \times i! \times \sum_{l=0}^{i}\sum_{j=0}^{L}\frac{S(K,i-l)}{l!}\frac{S(i,L-j)}{j!} \\ =&\sum_{i=1}^{n}\sum_{l=0}^{i}S(K,i-l)\frac{i!}{l!}\sum_{j=0}^{L}S(i,L-j)\frac{L!}{j!} \end{aligned} \]那么这个时候怎么算呢，你考虑，\(\sum_{l=0}^{i}\)时\(S(K,i-l)\frac{L!}{l!}\)与\(S(K,l)\frac{L!}{(i-l)!}\)的结果显然时相同的，\(\sum_{j=0}^{L}S(i,L-j)\frac{i!}{j!}与\sum_{j=0}^{L}S(i,j)\frac{i!}{(L-j)!}\)相同，所以原式可以变化为:
\[\begin{aligned} &\sum_{i=1}^{n}\sum_{l=0}^{i}S(K,i-l)\frac{i!}{l!}\sum_{j=0}^{L}S(i,L-j)\frac{L!}{j!} \\ =&\sum_{i=1}^{n}\sum_{l=0}^{i}S(K,l)\frac{i!}{(i-l)!}\sum_{j=0}^{L}S(i,j)\frac{L!}{(L-j)!} \end{aligned} \]这个时候你发现\(\frac{L!}{(i-l)!}\)和组合数是不是挺像的?
(组合数公式：\(C_{n}^{m} =\frac{n!}{m!(n-m)!}\))
是不是其实就是\(C_{i}^{l}\times l!\)?
另一个\(\frac{i!}{(L-j)!}\)同理。
故原式转换为：
那么这个时候你和前面那个前置知识\(2\)对比一下，发现式子可以转换为：
\[\sum_{i=1}^{n}i^KL^i \]其中\(S(n,m)\)为斯特林数，\(L\)为\(F_{n+2}-1\)
至此，我们便可以得到了这个题的\(30pts\)做法，我已经尽力了。