hdu4813 01背包+前缀和

题意：$A,B$两人,有$N$个事件，每件发生的概率都为$0.5$,若事件$i$发生，则$B$加$v_i$分数，若其不发生，则$B$不加分，给定一个概率$P$,问至少需要多少分数，才能使得$A $ 有$P$的概率分数不小于$B$

解：求出每种分值所对应的概率，问题就转换成，$B$获得每种分数$i$都有一概率$q_i$,求最小的$Ans$，满足$\sum_0^{Ans}q_i <=P$.

dp + 前缀和.

#include<iostream>

#include<cstdio>

#define rep(i,a,b) for(int i=(a);i<=(b);++i)

#define per(i,a,b) for(int i = (a);i>=(b);--i)

#define endl '\n'

using namespace std;

typedef long long ll;

const int maxn = 4e4+10;//40000

int T,n;

int v[40+10];

double dp[40+1][maxn],p;

int main(){

	scanf("%d",&T);

	int ans = -1;

	while(T--){

		scanf("%d%lf",&n,&p);

		rep(i,1,n) scanf("%d",&v[i]);

		rep(i,1,n) rep(j,0,maxn-1) dp[i][j] = 0;

		dp[0][0] = 1;

		rep(i,1,n)per(j,maxn-1,0){

			dp[i][j] += dp[i-1][j]*0.5;

			dp[i][j + v[i]] += dp[i-1][j]*0.5;

		}

		double sum = 0;

		for(int i = 0;i<maxn;++i){

			sum += dp[n][i];

			if(sum >= p){

			    ans = i;break;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

hdu4813 01背包+前缀和

最新文章

热门文章