题意

众所周知， $yang12138$yang12138是一名 $pupil$pupil。 他在 $codefire$codefire上注册了两个帐户。这两个帐户最初都处于0级，并且该级别最多为 $n$n。每次他赢了，等级会增加1，但如果他输了，级别就不会更改。 当在级别 $i$i使用帐户时， $yang12138$yang12138的获胜概率是 $p_i$pi​。达到 $n$n级的人在 $codefire$codefire中被称为 $GrandMaster$GrandMaster。 $yang12138$yang12138有作为一名 $GrandMaste$GrandMaster的梦想，所以他正在努力。 他的策略如下：
1.初始有两个帐号， $yang12138$yang12138会随机选择一个账户参加比赛。
2.假设他目前正在使用账户A，如果他赢了，他继续使用帐户A参加比赛。 否则他将使用其他帐户。
3.当他的任何账户达到 $n$n级时，立即停止，因为 $yang12138$yang12138已成为 $yang12138$yang12138。在每个级别获得 $yang12138$yang12138的概率。

你作为一个 $GrandMaster$GrandMaster，请计算 $yang12138$yang12138成为一个 $GrandMaster$GrandMaster的比赛次数的期望。

做法

考虑期望 $dp$dp.

$dp\left[i\right]\left[j\right]\left[0/1\right]$dp[i][j][0/1]表示第一个帐号级别为 $i$i,第二个帐号级别为 $j$j，且当前使用的是 $0/1$0/1的帐号的期望.

转移方程:

$dp\left[i\right]\left[j\right]\left[0\right]=dp[i+1]\left[j\right]\left[0\right]\ast p_i+dp\left[i\right]\left[j\right]\left[1\right]\ast (1-p_i)+1$dp[i][j][0]=dp[i+1][j][0]∗pi​+dp[i][j][1]∗(1−pi​)+1

$dp\left[i\right]\left[j\right]\left[1\right]=dp\left[i\right][j+1]\left[1\right]\ast p_j+dp\left[i\right]\left[j\right]\left[0\right]\ast (1-p_j)+1$dp[i][j][1]=dp[i][j+1][1]∗pj​+dp[i][j][0]∗(1−pj​)+1

联立两式消元即可.

代码

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 307;
db p[N], dp[N][N][2];

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    int T; scanf("%d", &T);
    while(T--) {
        int n; scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%lf", p + i);
        for(int k = 0; k < 2; k++)
            for(int i = 0; i <= n; i++)
                dp[i][n][k] = dp[n][i][k] = 0;
        for(int i = n-1; ~i; i--) {
            for(int j = n-1; ~j; j--) {
                dp[i][j][0] = (dp[i+1][j][0]*p[i]+dp[i][j+1][1]*p[j]*(1-p[i])+2-p[i])
                        /(p[i]+p[j]-p[i]*p[j]);
                dp[i][j][1] = (dp[i][j+1][1]*p[j]+dp[i+1][j][0]*p[i]*(1-p[j])+2-p[j])
                        /(p[i]+p[j]-p[i]*p[j]);
            }
        }

        printf("%.4f\n", dp[0][0][0]);
    }
    return 0;
}