一道让人不爽的动态规划题

一道让人不爽的动态规划题

题目是这样的，一条直线上有一些白色的圆。我们以三个圆为例，如下图：

O   O   O

现在让你把和黑色不相邻的圆涂成黑色。因为没有黑色，随意选择一个涂成黑色：

// 第一次：选第一个
*   O   O

// 第一次：选第二个
O   *   O

// 第一次：选第三个
O   O   *

我们的目标是涂涂涂，直到不能涂为止，最后输出黑色圆的个数的【数学期望】。

那我们把上面的情况补充完整：

// 第一次：选第一个
*   O   O

    // 第二次：选第二个
    *   *   O

    // 第二次：选第三个
    *   O   *

// 第一次：选第二个
O   *   O

// 第一次：选第三个
O   O   *

    // 第二次：选第一个
    *   O   *

    // 第二次：选第二个
    O   *   *

还要算数学期望，我把它加上去：

                                概率                黑圈数目
// 第一次：选第一个
*   O   O                       1/3

    // 第二次：选第二个
    *   *   O                   1/3 x 1/2           2

    // 第二次：选第三个
    *   O   *                   1/3 x 1/2           2

// 第一次：选第二个
O   *   O                       1/3                 1

// 第一次：选第三个
O   O   *                       1/3

    // 第二次：选第一个
    *   O   *                   1/3 x 1/2           2

    // 第二次：选第二个
    O   *   *                   1/3 x 1/2           2

期望为 E = (1/3)x(1/2)x2 + (1/3)x(1/2)x2 + (1/3)x1 + (1/3)x(1/2)x2 + (1/3)x(1/2)x2 = 5/3。

现在输入为一个数 N，求着 N 个白圆，涂黑后黑色圆的期望，比如当 N = 3，输出应为 1.6666666666666667。（只要你的结果相差不过 1e-6，就算对。）

费了九牛二虎之力，我终于把代码写好了：

#include <vector>
#include <cstdio>

using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))

double dp(int n) {
    vector<double> f(max(3,n+1));
    f[0] = 0.0;
    f[1] = 1.0;
    f[2] = 1.0;
    for (int i = 3; i <= n; ++i) {
        double p = 0.0;
        for (int j = 0; j <= i-3; ++j) {
            p += (1.0 + f[j] + f[i - 3 - j]);
        }
        p += 2.0 * (1 + f[i - 2]);
        f[i] = p/(double)i;
    }
    return f[n];
}

int main()
{
    while(1 == scanf("%d", &n)) {
        printf("%lf\n", dp(n));
    }
}

好开心！这好像是我实战中第一次做对动态规划。（如果对的话。）

但是，在最后几分钟，我提交失败了。因为我特么把代码提交到第三题了……

为什么 AtCoder 这么蛋疼。我已经干了好几次这样的蠢事了。

“从小就粗心。”

“妈的傻逼不长记性。活该！”

不能开心了.