投票游戏

题目大意：有 n 个人参加投票游戏。

每个人会投支持票或者反对票，第 i 个人投支持票的概率是p[i]

选出k个人使平票的概率最大。

全部的输入数据满足：

思路:根据样例我们可以发现先对所有的p[i]排序后，肯定是从头尾取几个人或者不取，这个性质或者说是推论可以用反证法证明（假定确定一部分人）,f[i][j]事实上是关于p[i]的次数为1的函数。

即最优选人方案一定是一部分前缀和一部分后缀组成的。

这时候对于前缀和后缀都来一次dp（O（n^2))算出概率之后再枚举（O(n））;

所以得到复杂度应为O（n^2),这是肯定可以过的

代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define maxn 2555
 4 int n,k;
 5 double p[maxn],a[maxn];
 6 double dp[maxn][maxn],f[maxn][maxn],ans=0;
 7 int main(){
 8 freopen("vote.in","r",stdin);
 9 freopen("vote.out","w",stdout);
10 scanf("%d%d",&n,&k);
11 for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
12 sort(p+1,p+n+1);
13 for(int i=n-k+1;i<=n;i++)a[n+1-i]=p[i];
14 dp[0][0]=f[0][0]=1.0;
15 for(int i=1;i<=k;i++){
16 for(int j=0;j<=i;j++){
17 dp[i][j]=dp[i-1][j]*(1.0-p[i]);
18 if(j>0)dp[i][j]+=dp[i-1][j-1]*p[i];
19 f[i][j]=f[i-1][j]*(1.0-a[i]);
20 if(j>0)f[i][j]+=f[i-1][j-1]*a[i];
21 }
22 }
23 for(int i=0;i<=k;i++){
24 double cnt=0;
25 for(int j=0;j<=k/2;j++)cnt+=dp[i][j]*f[k-i][k/2-j];
26 ans=max(ans,cnt);
27 }
28 printf("%.9f",ans);//看题目怎么说，我这里OJ交是要保留9位小数
29 return 0;
30 }