【题解】闯关游戏

题目描述

　　艾伦正在闯关。游戏有N个关卡，按照必须完成的顺序编号为1到N。每个关卡可以用两个参数来描述：prob [i]和value [i]。这些参数的含义如下：

　　每当艾伦尝试闯第i关时，他要么顺利通过，要么“挂掉”。他完成该关卡的概率总是prob [i] / 1000。（他总是尽力完成每个关卡。）在关卡i的末尾有一个宝箱，其中包含价值 value[i]单位的黄金。当艾伦完成关卡时，他从拿起该关卡的金币。

　　初始化时，艾伦从第1级关卡开始，艾伦没有黄金。对于每个有效的i，每当Allen完成关卡i时，他就会继续进行关卡i + 1，一旦完成第N个关卡，游戏就会结束。

　　每当艾伦“挂掉”时，下面4件事情会按顺序发生：

      　　1、除了艾伦携带的黄金，其他黄金都被从游戏中移除。

      　　2、艾伦目前所携带的所有黄金都“坠落”，“坠落”的地点就是艾伦“挂掉”的那个关卡的开头处。一旦艾伦以后再次达到这个关卡，即使在尝试闯该关卡之前，他也能够再次“捡起”上次“坠落”到这个地方的黄金。（请注意，如果他在到达这个关卡之前再次“挂掉”，这些黄金将永远消失。）

      　　3、所有箱子都添加了新的黄金，各个箱子黄金的量就是它们最初所含的量（相当于初始化各个箱子的黄金量）。

      　　4、艾伦回到了第1级的开头，且他没有携带金币。艾伦有无限条“生命”，“挂掉”后可以重新开始游戏。

　　通过上面的规则可以发现，艾伦“挂掉”后，最多只有一堆金币不在宝箱中，这一堆金币的位置就是艾伦最近“挂掉”所在的关卡的开头处。

　　为了避免精确错误，数据保证艾伦在一次性闯关全部成功的情况下赢得整个游戏的概率将至少为10 ^（ - 6）。你的任务是输出艾伦顺利闯完第N关时所携带的黄金的期望值。

 

输入格式

　　多组测试数据。

　　第一行，一个整数G，表示有G组测试数据。1 <= G <= 5。

　　每组数据格式：

    　　 第一行，一个整数N。2 <= N <= 1000。

     　　第二行，N个整数，第i个整数是prob[i]。1 <= prob[i] <= 1000。

　　     第三行， N个整数，第i个整数是value[i]。1 <= value[i] <= 1000。

 

输出格式

　　共G行，每行一个实数。答案误差不能超过0.00001.

 

输入样例

5

2

1000 500 

3 4 

2

1000 1 

3 4 

5

500 500 500 500 500 

1 2 3 4 5 

91

916 932 927 988 958 996 944 968 917 939 960 965 960 998 920 990 915 972 995 916 902 968 970 962 922 959 994 915 996 996 994 986 945 947 912 946 972 951 973 965 921 910 938 975 942 950 900 983 960 998 982 980 902 974 952 938 900 962 920 931 964 974 953 995 946 946 903 921 923 985 919 996 930 915 991 967 996 911 999 936 1000 962 970 929 966 960 930 920 958 926 983 

583 428 396 17 163 815 31 536 175 165 532 781 29 963 331 987 599 497 380 180 780 25 931 607 784 613 468 140 488 604 401 912 204 785 697 173 451 849 714 914 650 652 338 336 177 147 22 652 901 548 370 9 118 487 779 567 818 440 10 868 316 666 690 714 623 269 501 649 324 773 173 54 391 745 504 578 81 627 319 301 16 899 658 586 604 83 520 81 181 943 157 

2

250 750 

1000 1 

 

输出样例

10.0

3003.9999999999977

16.626830517153095

54204.93356505282

1067.6666666666667

 

题解

　　容易想到，当玩家在第$i$关挂掉时，如果他再次挂掉的关卡$j$满足$j<i$，那么他在第$i$关掉落的金币就消失了。

　　这样我们可以看出，设$dp[i]$为第$i+1$关挂掉的期望值，那么能对$dp[i]$做出贡献的只有满足$j<i$的$dp[j]$。

　　我们设$f[i]$为第$i+1$关挂掉的概率，容易得到$f[i]=\prod_{j=1}^{i}p[j] \times (1-p[i+1])$， 则$dp[i] = \sum_{j = 1}^{i} a[j] + \sum_{j = 1}^{i} f[j] \times dp[j]$，整理得到$dp[i] = \frac{\sum_{j = 1}^{i} a[j] + \sum_{j = 1}^{i - 1} f[j] \times dp[j]}{1 - f[i]}$。

#include <iostream>
#include <cstdio>

#define MAX_N (1000 + 5)

using namespace std;

int G;
int n;
double p[MAX_N];
double f[MAX_N];
double a[MAX_N];
double dp[MAX_N];
double s[MAX_N];

int main()
{
    cin >> G;
    while(G--)
    {
        cin >> n;
        p[0] = 1;
        for(register int i = 1; i <= n; ++i)
        {
            cin >> p[i];
            p[i] /= 1000;
            f[i - 1] = p[i - 1] * (1 - p[i]);
            p[i] *= p[i - 1];
        }
        f[n] = 0;
        for(register int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            a[i] += a[i - 1];
        }
        for(register int i = 1; i <= n; ++i)
        {
            dp[i] = (a[i] + s[i - 1]) / (1 - f[i]);
            s[i] = dp[i] * f[i] + s[i - 1];
        }
        printf("%lf\n", dp[n]);
    }
    return 0;
}

参考程序