列表

详情

NC25394. HRY and codefire

描述

As is all known, yang12138 is a pupil. He registered two accounts on codefire. The two accounts are both at level 0 initially, and the level is at most n. Every time he wins, the level will increase by 1, but if he loses, the level will not change. When using an account at level i, the winning probability of yang12138 is p_i.

Someone who reaches level n is called a GrandMaster in codefire. yang12138 has a dream of being a GrandMaster, so he is trying hard. His strategy is as follows:

1. Randomly pick an account to take part in a competition at first.
2. Assume that he is currently using account A, if he wins, he continues using account A to take part in competitions. Otherwise he will use the other account.
3. When any of his account reaches level n, stop immediately, because yang12138 has become a GrandMaster .

Given probability of winning of yang12138 at each level. As a GrandMaster, please calculate the expected competition times of yang12138 to become a GrandMaster.


输入描述

The first line of input contains an integer T, indicating the number of test cases.
For each test case there are two lines :
The first line contains an integer n.
The second line contains $n$ real numbers , indicating the probability of winning when using an account at level i.

输出描述

For each test case output a real number, rounded to 4 decimal places.

示例1

输入: 

2
1
0.5
2
0.5 0.5

输出: 

2.0000
4.6667

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 1912K, 提交时间: 2019-04-27 20:38:02 

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

int main()
{
	int T; cin>>T;
	while (T--) {
		scanf("%d",&n);
		for (int i=0;i<n;i++) scanf("%lf",&p[i]);
		
		for (int i=0;i<=n;i++)
			dp[i][n][0]=dp[i][n][1]=dp[n][i][0]=dp[n][i][1]=0;
		for (int i=n-1;i>=0;i--)
			for (int j=n-1;j>=0;j--) {
				double pi=p[i],qi=1-p[i];
				double pj=p[j],qj=1-p[j];
				dp[i][j][0]=(dp[i][j+1][1]*pj*qi+qi+dp[i+1][j][0]*pi+1)/(1-qi*qj);
				dp[i][j][1]=(dp[i+1][j][0]*pi*qj+qj+dp[i][j+1][1]*pj+1)/(1-qi*qj);
			}
		printf("%.4lf\n",dp[0][0][1]);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 34ms, 内存消耗: 2820K, 提交时间: 2019-04-27 18:38:51 

#include <bits/stdc++.h>
using namespace std;
double p[505],dp[505][505][2];
int main(){
	int T;cin>>T;
	while(T--){
		int n;scanf("%d",&n);
		for(int i=0;i<n;i++)scanf("%lf",&p[i]);
		for(int i=0;i<n;i++)dp[i][n][0]=dp[i][n][1]=dp[n][i][0]=dp[n][i][1]=0;
		for(int i=n-1;i>=0;i--){
			for(int j=n-1;j>=0;j--){
				dp[i][j][0]=(p[i]*dp[i+1][j][0]+(1.0-p[i])*p[j]*dp[i][j+1][1]+2-p[i])/(1.0-(1.0-p[i])*(1.0-p[j]));
				dp[i][j][1]=(p[j]*dp[i][j+1][1]+(1.0-p[j])*p[i]*dp[i+1][j][0]+2-p[j])/(1.0-(1.0-p[i])*(1.0-p[j]));
			}
		}
		printf("%.4lf\n",dp[0][0][0]);
	}
	return 0;
}

上一题

© 2024 nowcoder.com