【codeforces 442B】 Andrey and Problem

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

http://codeforces.com/problemset/problem/442/B (题目链接)

题意

n个人，每个人有p[i]的概率出一道题。问如何选择其中s个人使得这些人正好只出1道题的概率最大。

Solution

很显然的概率dp，过了样例即可AC。。话说我为什么要刷B题→_→

代码

// codeforces442B#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=200;double f[maxn][maxn],p[maxn][maxn],a[maxn];int n;int main() {scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lf",&a[i]);for (int i=1;i<=n;i++) {p[i-1][0]=1;for (int j=1;j<=i;j++) {if (f[i-1][j]<f[i-1][j-1]*(1-a[i])+p[i-1][j-1]*a[i]) {f[i][j]=f[i-1][j-1]*(1-a[i])+p[i-1][j-1]*a[i];p[i][j]=p[i-1][j-1]*(1-a[i]);}else f[i][j]=f[i-1][j],p[i][j]=p[i-1][j];}}double ans=0;for (int i=1;i<=n;i++) ans=max(ans,f[n][i]);printf("%.12lf",ans);return 0;}