【gmoj】【动态规划】投票

题目

P6296

---

解题思路

可以证明选的人一定是排序后两端的人

然后两个DP
f[i][j]表示选了前i个，有j个为好的
f[i][j]+=f[i-1][j-1]p[i]+f[i-1][j](1-p[i])
g[i][j]表示选了后i个，有j个为好的
g[i][j]+=g[i+1][j-1]p[i]+g[i+1][j](1-p[i])
最后统计答案时，枚举前面选了i个，且有j个为好的
ans=max(ans,f[i][j]*g[n-(m-i)+1][m/2-j])

---

代码

#include 
#include
#include
using namespace std;
int n,m;
double ans,da=1,a[2010],f[2010][1010],g[2010][1010];
int main()
{
	freopen("vote.in","r",stdin);
	freopen("vote.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	    scanf("%lf",&a[i]);
	sort(a+1,a+n+1);
	f[0][0]=1;
	for (int i=1;i<=m;i++)
	    for (int j=0;j<=m/2;j++)
	        if (j>0) f[i][j]+=f[i-1][j-1]*a[i]+f[i-1][j]*(1-a[i]);
	           else f[i][j]+=f[i-1][j]*(1-a[i]);
	g[n+1][0]=1;
	for (int i=n;i>n-m;i--)
	    for (int j=0;j<=m/2;j++)
	        if (j>0) g[i][j]+=g[i+1][j-1]*a[i]+g[i+1][j]*(1-a[i]);
	           else g[i][j]+=g[i+1][j]*(1-a[i]);
	for (int i=0;i<=m;i++)
	{
	    da=0;
	    for (int j=0;j<=m/2;j++)
	        da+=f[i][j]*g[n-(m-i)+1][m/2-j];
	    ans=max(da,ans);
	}
	printf("%.7lf",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34