题目链接：http://codeforces.com/problemset/problem/442/B
题目大意：有n个人，第i个人出一道题的概率是pi，现在选出一个子集，使得这些人恰好出一个题的概率最大。问最大概率。
可以仿照背包问题来做，即每个人可问可不问。
f[i][j]代表从前i个人里问j个人所获得1个题的最大概率。
f[i][j] = max{ f[i-1][j], f[i-1][j-1]*(1-p[i])+z[i-1][j-1]*p[i] };
z[i][j]为从前i个人里问j个人所获得1个题的最大概率对应的一个题也出不出来的概率。
转移见代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <cmath>
#include <numeric>
#include <iterator>
#include <iostream>
#include <cstdlib>
#include <functional>
#include <queue>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ size()
#define ST begin()
#define ED end()
#define CLR clear()
#define ZERO(x) memset((x),0,sizeof(x))
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double EPS = 1e-; int n;
double f[][],p[],z[][]; int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lf",&p[i]);
for(int i=;i<;i++) z[][i] = z[i][] = 1.0;
for(int i=;i<=n;i++){
for(int j=;j<=i;j++){
// printf("i=%d,j=%d\n",i,j);
// printf("f[i-1][j]=%f,f[i-1][j-1]*(1-p[i])+z[i-1][j-1]*p[i]=%f\n",f[i-1][j],f[i-1][j-1]*(1-p[i])+z[i-1][j-1]*p[i]);
if( f[i-][j]<f[i-][j-]*(-p[i])+z[i-][j-]*p[i] ){
f[i][j] = f[i-][j-]*(-p[i])+z[i-][j-]*p[i];
z[i][j] = z[i-][j-]*(-p[i]);
} else {
f[i][j] = f[i-][j];
z[i][j] = z[i-][j];
}
}
}
double ans = ;
for(int i=;i<=n;i++){
ans = max(ans,f[n][i]);
}
printf("%.12f\n",ans);
return ;
}