题解 P1984 【[SDOI2008]烧水问题】

· · 题解

话说这么多人怎么只找规律却不证明？ 加热方法很简单，加热第一杯，并依次传递到每一杯，然后加热第二杯并依次传递，直到加热最后一杯。这其实是个贪心，证明从略。

下面解决怎么算的问题。

方法一：时间O(n^2),空间O(n^2)

令f[i][j]表示第i杯水加热并传给第j杯后，第j杯的热量，（f[i][i]=\frac{420000}{n}，否则后面的递推式不能用）答案为\displaystyle\sum_{i=1}^{n}(f[i-1][i]+f[i][i])。

由定义可知：

f[i][j]=\begin{cases}\frac{420000}{n}&\quad(i=j)\\0&\quad(i=0)\\\frac{f[i-1][j]+f[i][j-1]}{2}&\quad\text{其它情况} \end{cases}

第三种情况是因为：

f[i][j]=f[i-1][j]+\frac{f[i][j-1]-f[i-1][j]}{2}=\frac{f[i-1][j]+f[i][j-1]}{2}

计算递推式即可。

方法二：时间O(n),空间O(1)

由前面的分析，我们有：

f[i-1][i]=\frac{f[i-1][i-1]}{2}+\frac{f[i-2][i]}{2}=\frac{f[i-1][i-1]}{2}+\frac{f[i-2][i-1]}{4}+\frac{f[i-3][i]}{4} \quad=\frac{f[i-1][i-1]}{2}+\frac{f[i-2][i-2]}{8}+\frac{2(f[i-3][i-1])}{8}+\frac{f[i-4][i]}{8} \quad=\dots \quad=\frac{k_1\cdot f[i-1][i-1]}{2}+\frac{k_2\cdot f[i-2][j-2]}{8}+\dots+\frac{k_j\cdot f[i-j][i-j]}{2^{2j-1}}+\dots+\frac{k_{n-1}\cdot f[1][1]}{2^{2n-3}} \quad=\displaystyle\sum^{i-1}_{j=1}(\frac{k_j}{2^{2j-1}}\cdot \frac{420000}{n})

由数学归纳法，我们得到k_i在意义上为：

边长为n的方阵中，除起点和终点外，其余各点都在左上——右下的对角线以下的一半（不含对角线上）的，从(n,n)到(n-i,n-i)的且只往上或右走的路径的数量，即：

k_i=C_{i-1}\text{（这里的C是卡特兰数！）}

卡特兰数？自己查！

于是：

f[i-1][i]=\displaystyle\sum^{i-1}_{j=1}(\frac{C_{j-1}}{2^{2j-1}}\cdot \frac{420000}{n}) \quad=\displaystyle\sum^{i-1}_{j=1}(\frac{\frac{\binom{j-1}{2(j-1)}}{j}}{2^{2j-1}}\cdot \frac{420000}{n}) \quad=\displaystyle\sum^{i-1}_{j=1}(\frac{[2(j-1)]!}{2^{2j-1}\cdot j!\cdot (j-1)!}\cdot \frac{420000}{n}) \therefore f[i][i+1]-f[i-1][i]=\frac{(2i-2)!}{2^{2i-1}\cdot i!\cdot (i-1)!}\cdot \frac{420000}{n}

令上式为g[i]，则：

\frac{g[i+1]}{g[i]}=\frac{\frac{(2i)!}{2^{2i+1}\cdot (i+1)!\cdot i!}}{\frac{(2i-2)!}{2^{2i-1}\cdot i!\cdot (i-1)!}}=\frac{2^{2i-1}(2i)!i!(i-1)!}{2^{2i+1}(2i-2)!(i+1)!i!}=\frac{2i-1}{2i+2}

而g[1]=\frac{210000}{n}， 于是可依次求出g的值，从而求出420000-\displaystyle\sum^{n}_{i=1}f[i-1][i]的值，此值即为答案。

做省选题的人不至于还要代码吧


#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    double ans = 0, f = 420000.00/n, g = 210000.00/n;
    for (int i = 1; i <= n; i++) {
        ans += f;
        f += g;
        g = g*(2*i-1)/(2*i+2);
    }
    cout << fixed << setprecision(2) << 420000 - ans << endl;
}