ACM模版

描述


题解

期望 DP 。

这里用 lose_[i][j] 表示镶嵌第 i 个孔用第 j 种宝石失败后会返回的宝石框的位置，dp[i] 镶嵌成功第 i 颗宝石的期望，那么对于第 j 种宝石来说，我们会得到如下方程：

dp[i]=dp[i−1]+C[j]+(1−prob[i][j])∗(dp[i]−dp[lose_[i][j]])
所以解方程后得出，
dp[i]=(dp[i−1]+C[j]−(1−prob[i][j])∗dp[lose_[i][j]])prob[i][j]

这里用一句话来说明一下第一个公式， dp[i] 一定是由 dp[i−1]+C[j] 转化而来的，但是在转化的过程中，存在 1−prob[i][j] 的失败率导致多花费 dp[i]−dp[lose_[i][j]] ……这个期望 dp 难度不大，公式也比较好理解，但是一定要注意温馨提示，注意精度，另外， INF 一定要开大，我的是 long long 的 0x3f3f3f3f3f3f3f3f ……一开始开了 int ， WA 了三组数据。

不错的题，十分有趣~(≧▽≦)/~

代码

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 105;
const int MAXM = 8;
const double ESP = 1e-9;
const long long INF = 0x3f3f3f3f3f3f3f3f;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int N;
int C[MAXN];
int lose_[MAXM][MAXN];
double prob[MAXM][MAXN];
double dp[MAXM];

int main()
{
    scan_d(N);
    for (int i = 1; i <= N; i++)
    {
        scan_d(C[i]);
    }

    int flag;
    for (int i = 1; i < MAXM; i++)
    {
        flag = 0;
        for (int j = 1; j <= N; j++)
        {
            scanf("%lf", prob[i] + j);
            flag |= abs(prob[i][j]) > ESP;
        }
        if (!flag)
        {
            puts("-1");
            return 0;
        }
    }

    int x;
    for (int i = 1; i < MAXM; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            scan_d(x);
            lose_[i][j] = i - 1 - x;
        }
    }

    dp[0] = 0;
    double tmp;
    for (int i = 1; i < MAXM; i++)
    {
        dp[i] = INF;
        for (int j = 1; j <= N; j++)
        {
            if (prob[i][j])
            {
                tmp = (dp[i - 1] + C[j] - (1 - prob[i][j]) * dp[lose_[i][j]]) / prob[i][j];
                dp[i] = min(dp[i], tmp);
            }
        }
    }

    printf("%.10lf\n", dp[MAXM - 1]);

    return 0;
}