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

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

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 这么蛋疼。我已经干了好几次这样的蠢事了。


“从小就粗心。”

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

不能开心了.


「Load Disqus | 加载评论」