I - Coins
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 100100 points
Problem Statement
Let NN be a positive odd number.
There are NN coins, numbered 1,2,…,N1,2,…,N. For each ii (1≤i≤N1≤i≤N), when Coin ii is tossed, it comes up heads with probability pipi and tails with probability 1−pi1−pi.
Taro has tossed all the NN coins. Find the probability of having more heads than tails.
Constraints
- NN is an odd number.
- 1≤N≤29991≤N≤2999
- pipi is a real number and has two decimal places.
- 0<pi<10<pi<1
Input
Input is given from Standard Input in the following format:
NN
p1p1 p2p2 …… pNpN
Output
Print the probability of having more heads than tails. The output is considered correct when the absolute error is not greater than 10−910−9.
Sample Input 1 Copy
3
0.30 0.60 0.80
Sample Output 1 Copy
0.612
The probability of each case where we have more heads than tails is as follows:
- The probability of having (Coin1,Coin2,Coin3)=(Head,Head,Head)(Coin1,Coin2,Coin3)=(Head,Head,Head) is 0.3×0.6×0.8=0.1440.3×0.6×0.8=0.144;
- The probability of having (Coin1,Coin2,Coin3)=(Tail,Head,Head)(Coin1,Coin2,Coin3)=(Tail,Head,Head) is 0.7×0.6×0.8=0.3360.7×0.6×0.8=0.336;
- The probability of having (Coin1,Coin2,Coin3)=(Head,Tail,Head)(Coin1,Coin2,Coin3)=(Head,Tail,Head) is 0.3×0.4×0.8=0.0960.3×0.4×0.8=0.096;
- The probability of having (Coin1,Coin2,Coin3)=(Head,Head,Tail)(Coin1,Coin2,Coin3)=(Head,Head,Tail) is 0.3×0.6×0.2=0.0360.3×0.6×0.2=0.036.
Thus, the probability of having more heads than tails is 0.144+0.336+0.096+0.036=0.6120.144+0.336+0.096+0.036=0.612.
Sample Input 2 Copy
1
0.50
Sample Output 2 Copy
0.5
Outputs such as 0.500, 0.500000001 and 0.499999999 are also considered correct.
Sample Input 3 Copy
5
0.42 0.01 0.42 0.99 0.42
Sample Output 3 Copy
0.3821815872
double p[maxn];
double dp[3050][3050];
int n;
题意：给N个硬币，每一个硬币扔向空中落地是正面朝上的概率是p[i] ，让求扔了N个硬币，正面的数量大于背面数量的概率。
很裸的概率DP，我们思考一下状态和转移方程。
我们这样定义状态，定义dp[i][j] 为到第i个硬币时有j个是正面的概率。那么所求答案为sum{ dp[n][i] || (n+1)/2<=i<=n}
题目说了n为odd，
那么状态转移即为： dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1.0-p[i]);
意思为，到了第i个硬币时，j个正面朝上的状态可以由以下两个状态转移过来：
1、第i-1个硬币的时候，有j-1个正面朝上的，第i个硬币也正面朝上。
2、第i-1个硬币的时候，有j个正面朝上的，第i个硬币反面朝上。
然后初始状态定义
dp[1][1]=p[1];
dp[1][0]=1.0000000-p[1];
注意处理下边界情况就好了。
细节见AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
double p[maxn];
double dp[][];
int n;
int main()
{
gg(n);
repd(i,,n)
{
scanf("%lf",&p[i]);
}
dp[][]=p[];
dp[][]=1.0000000-p[]; repd(i,,n)
{
for(int j=;j<=i;j++)
{
if(j==)
{
dp[i][j]=dp[i-][j]*(1.00000-p[i]);
continue;
}
dp[i][j]=dp[i-][j-]*p[i]+dp[i-][j]*(1.0000-p[i]);
// dp[i][j-1]=dp[i-1][j-1]*(1.000000-p[i]);
}
}
double ans=0.0000000000000000000;
for(int i=(n+)/;i<=n;i++)
{
ans+=dp[n][i];
}
printf("%.10lf\n", ans);
return ;
} inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '');
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * - ch + '';
}
}
else {
*p = ch - '';
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * + ch - '';
}
}
}