找玩具

题目描述

在游戏开始之前，游戏大师在房间的某些地方隐藏了N个玩具。玩具编号为1到N。您的任务是尽可能多地找到这些玩具。

你没有任何辅助信息就能找到第i个玩具的概率是p[i]％。您每找到一个玩具后，有可能可以得到一些辅助信息，这些辅助信息是告诉您其他某些玩具所在的位置。如果您已经知道玩具的位置，您一定会找到它。

给出二维数组clue[1…N][1…N]，其中clue[i][j]=‘Y’表示若找到第i个玩具则会告诉您第j个玩具的具体位置；clue[i][j]=‘N’表示第i个玩具没有第j个玩具位置的辅助信息；

你的任务是计算您在游戏中找到的玩具数量的期望值。

输入格式

多组测试数据。

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

每组测试数据格式如下:

    第一行，一个整数N。1 <= N <= 50。

讯享网

    第二行，N个整数，第i个整数是p[i]，0 <= p[i] <= 100。

    接下来是N行N列的二维数组clue。

输出格式

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

输入样例

10 1 50 Y 2 100 50 YN NY 3 100 0 0 YYY NYY NNY 3 0 0 0 NNN NNN NNN 10 11 66 99 37 64 45 21 67 71 62 NYYNYYNNNN NNNNYNNNYN YNNYYYYYNN YYNYNNNNYN NYNNNNNNNY YNYYNNYNNY NYNNYYYYYY NYYYYNNNNN YYNYNNYYYN NNYYNYNYYY 3 50 50 1 NNY NNY NNN 50 43 29 22 5 34 0 21 25 31 1 0 3 6 31 2 44 40 41 1 35 32 0 38 3 8 45 38 49 15 48 42 42 13 37 36 8 23 24 38 8 22 5 8 35 50 33 16 37 44 0 YYNNYYNNYYNYNYNYNNNNNYYYYNNYYYNNYYNYYYYNNNYYNNNNNN YYNYYNNNYNYNNYNNYNNYYYYNYYNNYYYNNYNNNYNNYYYNNYYNNY NNYNNYYNNNNYYNYYYNYNNNYNNNYNNNNNYNYYYYNNNNYYNNYNYN YNNNYNYNNNYNNNYNNNYYNNYYNYYNNYNYYYYNYNYNYNYNYNYNNY NNYNNYNNNNNYYYYYYNYNNYNNNNYNNNNNYYNNYYNNYNYNYYYYNN YYYYNYNNNYNNYYNYNYYYNNNNYNYYNYNNNNNYNNNNNYNNNNYYYN YYYNNNYYYYNNNNNNYYNNNNNNNNYYNNNNYYNYYNYYYNNNYYYYYY NYNNYNYNYYNNYYNNYYYNYNNYYYNYYYNYNNYNYNNNNNNNYNYYNN YYYNNNYYNNYNYNYNYNYYYNYYNNYNYNYNNNNYNNNNNNYYNNYYYY YYYYYYNNYNYYYYYNYYYNYNYYYNNNYNYNYYNNYNYYYYYNYNYNNY NYNYYNYNYNNYNNYNNNYYYYNNYYYNYNNYNNYNYYNNNNYYNNYNYN YYYYYYYYNNNYYYNNNYNYYNYYYNNYNNNNYNNNYYYNNYNYYNNYYN NNYNNNNYYNYNNYNNNYYNNYNNYYYNNYYYYNYNNNNYNNNYYYNNNN NYYNNNNNNYYYYNYYYYYYYYYNYYYNYYNYNNYYYNYNYYNYYYYYYN YNYNYNNNNYNNNYYYYNNNYYNNNYYNNNNYNNYYYYYYYYNNYYNNYY NNNNYNYNNNYNYYYNNYYYNNYNYNNYYNNNYNNNNYYYNYNYYYNYNN YNYYYNYNYNNYYNYYYNNNYNNNNNNNYYNYNYYNNYYYNNNNYYNNNY YNYNYNNYNNYYNYYYNYYYYYYYNYYYYNYYNYYNYNNYNNYNYNYYYY YNNYNNYYYYYYNYNYNNYNYNYYYYYNYYNYNNYNNNNNYNNYYYYNNN NYNNYYNYNNNNNYYYNNYYNNYNYNNNYYNYNYYYYYYYNNNNNNNNYY YNYNNYNYNNYYNYNNYNNNNNNYNNNYYYNNYYNNNNYYNNNNNNYNNY YYNYYYYYYNYYYYYYNYYYNNYYNYNNNYYYNNYNYNYYYYYYYNNYNN NNNNYYNYNNYYYYNNYYNNYNNYYYNNYYYNNNNNNNNNNYYNYNYYNN NYYNNYNNNYYYYYYNYYYNYNYNYYYYYNNNYNNNNYYYYNNNYNNYYN YNYYNYYNNNYYYYNNNYYNYNNNYNYNNNYYYNNYYYNYYNNNYNYNNY NYYYNYYNYYNYNYNNNNYNNNNYNYNNYNNNNNYYYYYYYYYYNYYNNN NNNYYYYYNNYYNNYYYYYYYYYYNNNYNNNYYNYYYNYYNYYYNNYYYN YNYNNNNNNYYNNNNNYNNNYYNNYYNYYYNNNNNNYYYYYYYNYYYNYY NYYYYYYNYNYYNNNNNYYYYNYYNNYNYNYNNNYNYYYNNYNNYYNYYN YNYYYYYYNYYYNNYYNNYNNYYNYNNYNYYYNYNYNYNNNYNYYNNNYN NYNYYYYYNNNNYNYNNNNNYYYNNNYNYYYNNNYNNYYNNYYNNYNNYY NNNYYNYYYYYYYYNNNYYYYNYYYYYYNYNNNYYNNYYNYYYYNYYNYY YYNNYNNYNYYNYYYNYYYYYYYYYYYNNNNYNNYNYNYNNYYYNYNNYY YNYNNYNYYYYYYNNNYNYYNYNYYYYNNYNYNNYNYYYYYYYYYNNNNY YNNNNNYYYNNYYYYNNYYNYNNNYYYNYNYNYNNYYYNNYNNYYNNYYN NYNYYNYNNNYYNNYNNNNYNYYYNYYNNYNNYNNYYNNNNYYNYNNNYY YNNYYNYNNNNNNNYNNNYYYNNNYNYNYYNYNYYYNYNYYYYYYYNYNY YNYNNYYNNNYNNNNYYYNNYYYNNYNNNNNNYNYNYNNNYNNNNYNNYN YNYYYYYNNYYYNNNYNYYYNYYNYNYYNNNYYNYNYYYNNNNYNYYNYN NYNYNNNYNYYYYYYNYNYNNYNYYYNYYYNYNYNNNYNNNNNYNYNYNN YYNYYNNYYYYYYYYNNYNYYYYYNYYYYYNYYYNYNNNYYNNYYYNNYY YYNNNNNYYNYNYNNNNNYNNYYNNYNYNNNYYNYNYNNYNYNNNYNNNY YNYYNYYYNYYNNYYYNNNNYNYNYYYYNNNNYNYYYNNNNNYNNNNYYY NNYYYYNYYNYYNYYNNYNNNYNNNNNYNNNYNYYNNNYNYNYNYNNYYN YYNNYNYYNYYYYYNYYYNNNYYNYYYNYYYNNYYYNYYNNYNYNYNNNN NYNYNYNNNYYYYNYYNYNYYYYNYYNNYYYYNNNNNNNNNYYYNYYYNY YNYNNYNYNNNYNYYNYNNNNNYYYYNYNNNNYNNNYYNNNYYNNNYYNN NYNNYYYNYNNYYNNNYYNYNNYNYNNNNYYNNYNYNNYYNYNNNYNNNN NNYNYYNYNYYNYYNYYYYYYNNNYNYYYYNNYNYYYNYNYNYNYNYYYY NNNYNNYYYYNNYYYYYNNYYYYYYNNYNNNYYYYYYNNYNYYYNNYNYN 50 17 4 18 9 16 16 15 14 9 0 1 14 2 12 4 1 9 17 17 9 16 4 9 2 0 3 4 7 17 6 1 10 13 2 0 3 10 10 9 2 7 18 7 16 9 13 19 5 18 10 YYNNYYNYNYYNYYYYYYYYNNNNYYYNYNYYYYNNYNNYNYYYNNYNYN YYNNYYNYNNYYNYYNNNNNNYYYNNNNNYNNNNNNYNNNNNYYYYYNNN NYYNYNNYNNNYYYYNYYYNYNNYYYYYYYYYNNYYYYNYNYYYNYNYYN YNNNNNYNNYYYNYYNNNYNYYNYYNNNYYNYYNNYNNYNNNYNNYNNNY NNNNNYYYNNNYNYNYYNNYNNYYNYNNNYNYNYNYYNYYYNYNYNYNNY NNNNYYNYYYNYYNNYYYNNNNYYYNYNNNYNYYYYYNNYNNNNNYNNNN YNNNYNYNYNNNNYNYNNNNYYYNYYYNNYYNYNNNYYYYNNNYYYYYNY YYNNYYYYYNYYNNNNNNNYNNNYNNYNYYYNYNYYYNNNYNNNYYYNNN NNNYNNNYNNNNYYNNYNNNYYYNNYYNYNYNNYYYNNYNNYNNYNYNNN NYYYNNYYNNYNNNNYYNNYNYNYNNYNNNNYNNNNYNYNYNNNNNNNYY NNNNYYNYYNNYNNNNYNYNNYYNNYNYNNYNNYNNYNYYYYNNYYYNYN YNYNNNYYYYYYYNYNYNNYYYYYNNYNYYNNYNNYNYYNYNNNNNYNYY NYYYYNNNYYYYYYNNNNYYYYYYNYYNNYYYNNNNNYNYNYNNNNNNNY YNNYYNYYNNNNYYNNYYNYYYNYNNYYNYYYNNNYYYNYYYYYNYYNYY YNYNYYNYYYYYNNYNNNNYNNYYYNYNNYYNNNYNNNNYNYNNNNNYYY YNYNYNNNYNYNYNNYNYNNNYNYNNNNYYNYYYYNYYYYNYNYNYYNYN NNNNYYNNYNNYNYYNYYYNNNNNYNNNNNNNYYYYNNYYYYNNNNNNYY NYNNYYNYNNYNYYYYNNYNNNNNYYNYNNNNYYNYYNYYYYNNNNYNYY NYNNNYNYYYYYYNNNNYYNNNNYNYYYYNNNYYNYNYYYNNNNYYYNNY YNNYYYNYYYNYNYYYYYYNNYYNYNNYYNNNYNNNYYNYNYYYYYYYYN NYYNYYYNNYNNYNYYNNNNNYYYYYNYYYYNNYYNYNYYYYNNYNYYYY YNNYNNNYNNYNYYNNYYYNYYYYYNNNNNYYNYYNYYNNNNYYYYNYNN NYNNYYYNNNNNNYYNNNYNNNYYYNYYYNNNYNYYNYYNYYNYYNNYYN YNYNYNYYNNYNYNYYNNYYYYYNYNNYYNNNYYNNYYYNNYYYNYYYYY YNNNYYYNYNNNYYYNNNNNNYNYNYNYNYYYYYNYYYYNYNNYYYYYYY YNNNYNYYYYNYNNNYNYNNYYNNYYYNYNNYYNYNNYNYNNNNYYNYNY YNNYNYNNYYNYYYYNYYNYNNNNNNYNYYYNNNNNNNYNYNNYNYNYYN YYNYYNNNYNNYNYNNYYYNYNNYNYYYYNNYYYYNYYYNYYNNNNYYNN YYNYYNNNNYNNYYYYYNYNYNYYYYYNYYNNYYNNNNNYYNYNNNNNYY YYNNNYNYNNYYYNYYNYYYYNYNYNNYNYYNYNYYNYYYYYYYYYNYNN NYNYYYNYYNNYYNNNNNYNNYNNYYNNYYYYNNNYYNYNNNYNNYNYNN NYYYYNYYNNNNYYYNNYNYNNYNYNYYNYNYNNYNNNNNYNYNYNYYYY YNYYNNNNNNYYYYYNNNYNYNNNNNYNNNYNNNNYNYNYNYNNNYNYYY YYYNYYNNNYNYYYNNNYNYYNYNNYNYNYNYNNYNYYNNYNYNNNNYNN NYYNNYNYNYYNYYNNNYNYYYNNNNNYYYYNNYYNNYYNNNYNYYYYYN YNNYYNYYYYYYYNNNNNYYYYNYYNNNYNNNYNYYYNYYYNYNNNNYNN NNYYNYNYYNNYNNYYNNNNNYNYNNYYYNNYYNNYYNNYNNYYYYYNNY NNYYYYNNYYYYNYYYNYYNNYYYYNYNYYNNNNNNYNYNNNYYYNYNYN YNNNNYNYNYNYYYNYYYYYYYYNYYNYNYYYNYNYYYNNYYNNNNNNYY YNNYYYYYYNNNYNNYYYYYYYNNYYNYYNNNNNYNNNYNNYNNNNNYYY YYNNYNNNNYNNNNNYNNNYNNYNNYYYNNYYNYNYYNYNNNNNYNYYNN YNNYNNYNNNYYYNNNNNNYYNYNYYNYYNYNYYNNYNYNYNYYNYYYNN YYNNYNNNYYNNYNNNYNNNNNYYNYNYYNNYNYYYYYNYYYYNNNYYNN NNNYYNYNNYYNNNNYNYNNYYNNNNNYNNYYYYYYYNNYNYNYNNYNNY NNYNNYYYNNNYNNYNYNNNYNNNYYYNNYNNNNYNNNYYYNYYNYNNNY YNNNYNNYNNYNYYYNNNNNNYYYYYYYNNNNYYYYNYNNNNNYYNYYNY YYYNNYNYNYYNYYYNYNYYNYYNNNNYNYYNYYYYNNYNNNNYNNYNNY YNNYYNNYNYNYYNYYNNYYYNNYNNNYYYYNYNYNYYNYYNYYNNYYYY YNYNYYYYNNYYYYYYNNNNNYYNNNNYYNNNNNNYYYNNNNNNYNYYYN NNYYNYNYNNNNNNYNYYYYNYNYYNYYYNYNYYYYNNYNNYNYYYNNYN 50 33 11 4 49 43 24 50 25 20 15 44 27 5 50 35 19 18 24 17 22 37 44 10 1 7 34 49 48 28 26 45 8 40 25 18 18 21 21 14 17 21 20 27 29 19 6 28 49 26 31 NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNNNYNNNNNNNN YNNNYNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNYNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNYNNNNNNNNNNNNNNNNNY NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNYNNNNNNNNNNNN NYNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNNNYNNN NNNNNNNNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNNNNNYNNNNN NNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNNYNNNNNYNNNNN NNNNNNNNNNYNNNNNNNYNNNNNNYNNNNNNNNNNNNNNNNNNNNNNYN NNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNN YNNNNNNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNYNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNYNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNY NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNYNNNN NNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNNNNNNNN NNNYNNNNNYNNNNNNNNNNNNNNNNNNNNYYNNNNNNYNNNNNNNNNNN NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNYNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNYNNNN NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNYNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNY NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNYNNNNNNNNNYNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYYNNNN NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNN NNNYNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNYNNNYNNNNNNNNNNNNNNNYNNNNNNN NNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNYNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNYYNNNNNNNNNNNN NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNYNNNNYNNNNNYNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNN NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNYNNNNN NNNNNNNNNNNNNNNNNNYNYNYNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNYNNNNNN NNNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNYNNNNNNNYNNNNNNYNN 50 61 24 45 93 76 39 79 84 77 68 43 100 21 26 27 82 31 70 23 89 98 74 87 75 73 39 91 15 52 46 15 58 93 73 75 73 30 59 89 87 55 5 46 28 31 36 98 12 42 61 NNNNNNNNNNYNNYNNNNNYNNNNNNNNNNNNNNNNNNYNNNNNNNNNNN YNNNYNYNNNNNNYNNNNYNNNYNNNYNNNNYNNNNNNNNNYNYYYYYNN NNNYNNYNYNYNNNNNNNNNNNNNNNNYNNYYNNNNNYNYNNNYNNNYNN YNNYNNNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNNNNNNNN NNNNYNNNYYNNNNNNNYNNYNYYNYNYNNNNNYNNYNYNYNNNNYNNNN NNYNNNNYNYNNNNYNNNNNYNYNYYNNYYYNNNNNNNNNYNNNNNNNNN NNNNYNNNNNNNNNNYYYNNNNNNNNNNNNNNNNNYNNNYYNYNNNNNNY NYNYNNNNNNNNNNNNNNNNNNNNNNYYNNNNNNNNYYNNNNNYNNNNNN NNYNYNNNNNNYNYNNNNNYYNNYYNNNNNNNNNNYYNNNNNNNNNNYNY YNNNNNNYNNNYNNNNNNNNYYNNYNNNYNNYNNNNNNNNYYNNYYNNNY YNNNNYNNNNNYNNYNNNYNNYNNNYNNNNNNYYNNNNYNNNNYNNNNNY NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNYYNYNNNNNNYNNNNNNN YNNNNNNNYNNNNNNNYNNNNNYNNYNNNNYNNNNNNNNNNNNNNYNYNY NNNNNNNNNYNYNNNNNNNNNYNNNNNNNNNYYNNNNNNNNNYNYNNNNN NNYNNNNNNNNNNNYNNYYYNNNNNNNNNYNNNYNYNNNNNYNNNNNYYN YYNNNNNNYNNNNNNNNNNNNNNNNNNYNYNNYNYNYNNNNNNNNNNNNN NNNNYYYNNYYNNNNNNNNNNYNYNNNNYNNNNNYNNNNYNNNNNYYNNN YYNNNNNNYNNYNNNYNNNYNNNYYNNYNNNNNNNNNNYNNNYNNNYNNY NNNNYNYNYNYNYNNNNNNYYYNNNYNNNNNNNNNNNNNNNNYNNNNNNN YNNNNNNNNNYNNNNNYNNYNYNNNNNNNNNYNNNNYNNYNYNYNNYNYY NNNNYNNNNNNNNNYNNNNNNNNNYNNYNNNNNNYNNNYNNNNNYYNNNN NNNNNNNNNNNNNNNYNNNNYNNNNNNNNNNYNNYNYYNNNNNYYNNNNN NNNNNNYNYNYYNNNNNNNNNNNNNNNYNNNNYYYYNNYYNNYNNNNNNN NNNNNNNNYNNNNNNNNNYNYNNNNYNNYNYNYNNNNNNYNNNNNNYNNN NYYYNYNNNYYNNNNYNNNNNNNNYNNYNNNNNYNNNNYNNYNNNNNNNN NNNNNNNNNYNNNNNNNYNYNYNNNYNNYNNNNNNNNNNNYNNNNNYYYN NNYNYNNNNNNNYNNNNNYNNNNNNNNNNNNNNNYNYYNNNNNYNYYNYY NNNNYNNNNNNNNNNNNNNNYYNNNNNYNNYYNNNNNNNNNNNNYYNNYN NNNNNNNNYNNNNNNNNNNNNYYNNNNNNNNYNYNYNNNNNNNYNNYNNY NNNNNNNNNNNNYNYNNNNNNNNNNNNYNNNYNNNNNNNNNNNYNNNNNY NNNNYNYYNNNNNYYNNNNNNNNYNYNNNNNNNNNNNYNNYNYYNNNNNN NNYNNNNNYYYNNNNNNYNNNYNNNNYNNNNNNNNYYYNNNNNNNNNYNN NNYYNYNNNYNNNYNNNNNNYNNYNNNNNNNYNNNNNNNNNNNNYNNNNN YNNNNNYNNNNNYNNNNNNNYYYYYNNNYNNNYNNYNNNYNNNYYNYNNN NNNNNNNNNNNNNYYNYNNNNNNYNYNNNNNNNNNNYNNYYNNNNNNYNY NNNNNNYNNYNNNNNYNNNNNNNNNYYYYNNNYNNYNYNNYNNNNNYNNN NYNNNYNYNNNNNNYYNNNNNNNNNYYYNNYNNNNNNNNNNNYNNNNYNN NNNNNNYNNNNNNNNYNNNNNNNNNNNNNNYNNNNYNNNYNNNNNYYNNN NNNNNNNNNNNNNYYNNNNYNNNNYNNYNNYYNNNNYNYNNNNNNNYNNN NNNNNNNYYNNNNNNNNNNYYNNNNNYNNNNNNNNYNYNNNNYNNNNNNN YNNYNNNNNNNNNNYNNNNNNNYNNNNNNNNNNNNYNNYNYNNYNNNYNN NNNNNNNNNNNNNNNYNNYNYNNNNNNNNNNNNNNNNNNNNNNYYNNNYN NNNYNNNNNNNNNYNNNNYNNNNYNNNNNNNYNNYNNNNNNNNYNYNNNN YNNNYNNNNNNNNNNYNYNNNNNNYNNNYNNNNNNNYYYNNNNNNNYNYN YNNNNNNNNNYNNNYNNYNNNNNNYNNNYYNYNYNNNYNYNNNNNNNNYN NNNNNNYNNNNYNNNNNYNNNNYNNNYNYNNNNNNNNYNNNNNNNNNNNY NNYNNNYNNNYNNNNNNNNYYNNNNNNNNNYNYYNNNNNNNYYNNNNNYN NYYYYNNNNNYYNNNNYYNNNNYNNNNNYNNNNYNYNNYNNNNNNNNYNN NNNNNYNNNYNNNNNNNYNYYNNNNNNNNYYNNNYYNNYYNNYNYNNYNN NNYYNNNNNNNNYNNNNNNNNNYNNNNNNNNNYNYNNNNNNNYNNNNNNN 

输出样例

讯享网0.5 1.5 3.0 0.0 9.7332 1.7525 49.1165 49.631 46.021 50.0 

解题思路

题目大意：求找到玩具数量的期望值。
如果我们从整体正面考虑问题，是十分困难、复杂的（当然也是可行的）。所以我们单独考虑每一个玩具找不到的概率，最后用1减去即为答案。

我们思考，在什么情况下找不到第$i$种玩具呢？
我们知道，找到一个玩具的途径是直接寻找它，也可以通过找到其它玩具而找到它，只有当可以找到它的玩具都找不到且直接寻找找不到它时才算是真正的找不到第$i$个玩具。
如果我们可以通过第$k_1,k_2,k_2\cdots k_m$个玩具找到第$i$个玩具，那么只有当第$k_1,k_2,k_2\cdots k_m$个玩具都找不到，且第$i$玩具也找不到时，才算是真正的找不到第$i$个玩具，然而这第$k_1,k_2,k_2\cdots k_m$个玩具又可以通过其他一些玩具找到他们，那么又要让这些玩具找不到时，才算是真正的找不到第$i$个玩具。

下一步，第$i$个玩具找不到的概率是多少呢？
从上面的分析我们已经知道，只有当可以找到它的玩具都找不到且直接寻找找不到它时才算是真正的找不到第$i$个玩具，那么设找不到第$i$个玩具的概率为$prob(i)$，$prob(i)=(1-p[i]\%)+prob(k_1)+prob(k_2)+\cdots +prob(k_m)$，由此我们可知，本题的正确解法就是dfs。

我们通过题目给出的矩阵，对每一个玩具进行dfs，然后求出找不到这个玩具的概率，最后用1减去即可得出答案。

（这题的样例好大啊！过了样例就能过所有测试点了）

代码

#include<iostream> #include<fstream> #include<algorithm> #include<string> #include<cstring> #include<cstdio> using namespace std; int G,N; int p[55]; string s; bool clue[55][55],vis[55]; double ans; double dfs(int now) { 
    vis[now]=1; double temp=1.00-p[now]*0.01; for(int i=1;i<=N;i++) if(clue[now][i]==1&&vis[i]==0) temp*=dfs(i); return temp; } int main() { 
    freopen("2823.in","r",stdin); freopen("2823.out","w",stdout); cin>>G; for(int gr=1;gr<=G;gr++) { 
    cin>>N; ans=0.0; for(int i=1;i<=N;i++) cin>>p[i]; for(int i=1;i<=N;i++) { 
    cin>>s; for(int j=1;j<=N;j++) { 
    if(s[j-1]=='Y') clue[j][i]=1; else clue[j][i]=0; } } for(int i=1;i<=N;i++) { 
    memset(vis,0,sizeof(vis)); ans+=1.00-dfs(i); } printf("%.6lf\n",ans); } return 0; }