动规背包思想RE求解
  • 板块学术版
  • 楼主Milky_Cat
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/12/17 17:13
  • 上次更新2023/10/24 07:25:20
查看原帖
动规背包思想RE求解
906320
Milky_Cat楼主2022/12/17 17:13
#include<bits/stdc++.h>
using namespace std;
int n;
double p[6005],q[6005];
double f[100005][2]; 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i];
		q[i]=1-p[i];
	}
	int tal=1,sx;
	double sum=0.000;
	if(n%2==0)sx=n/2-1;
	else sx=n/2;
	f[0][0]=1.000;
	f[0][1]=-1;
	for(int i=0;i<n;i++)
		for(int j=0;j<tal;j++){
			if(f[j][1]==sx)continue;
			f[tal++][0]=f[j][0]*p[i];
			f[tal-1][1]=f[j][1];
			f[tal++][0]=f[j][0]*q[i];
			f[tal-1][1]=f[j][1]+1; 
		}
	for(int i=0;i<tal;i++)if(f[i][1]<=sx)sum+=f[i][0];
	printf("%.6lf",sum);
}
2022/12/17 17:13
加载中...