https://www.luogu.com.cn/problem/AT_dp_i 第1题 抛硬币 查看测评数据信息
有n个质地不均匀的硬币,抛第i枚硬币器正面朝上的概率是p[i],反面朝上的概率是1-p[i],扔完n个硬币后,求正面朝上的个数大于反面朝上的概率是多少。结果保留三位小数
输入格式
第一行一个整数n,表示有n枚硬币
第二行n个实数,表示第i个数的正面朝上的概率
1<=n<=2999,0<p[i]<1
输出格式
一个实数
输入/输出例子1
输入:
3
0.30 0.60 0.80
输出:
0.612
输入/输出例子2
输入:
1
0.50
输出:
0.500
样例解释
无
看到概率,就往dp方面想
写dp前可以先看范围
这题O(n^2),不难想到第一维肯定是对于前i个硬币。
状态要转个弯,直接求正面>反面比较难算,我们可以求出正面数量,用n-正面得出反面,就可以比较了
状态就出来了,f[i][j]: 考虑前i个硬币,有j个正面朝上的概率
转移:按照第i个硬币正反讨论:
1.正: f[i-1][j-1]*p[i]
2.反: f[i-1][j]*(1-p[i])
答案:
f[n,n/2+1~n]
这题类似背包,就是选和不选
#include <bits/stdc++.h> using namespace std; const int N=3010; int n; double a[N], f[N][N], ans=0; int main() { scanf("%d", &n); for (int i=1; i<=n; i++) scanf("%lf", &a[i]); f[0][0]=1; for (int i=1; i<=n; i++) for (int j=0; j<=i; j++) { if (j>=1) f[i][j]=f[i-1][j-1]*a[i]; f[i][j]+=f[i-1][j]*(1.0-a[i]); } /* for (int i=1; i<=n; i++) { for (int j=1; j<=i; j++) printf("%.3lf ", f[i][j]); printf("\n"); }*/ for (int i=n/2+1; i<=n; i++) ans+=f[n][i]; printf("%.3lf", ans); return 0; }
标签:概率,硬币,int,正面,dp,朝上 From: https://www.cnblogs.com/didiao233/p/18363640