当前位置: 代码迷 >> 综合 >> poj-2151-概率dp
  详细解决方案

poj-2151-概率dp

热度:63   发布时间:2023-12-19 11:19:01.0

题目大意:

给你m,t,n,代表t个队伍,做m道题,对于所有的队伍,全部做对1道或者以上的题目,并且至少有1个队伍做对n道题目的概率。

做法:

p[i][j]代表第i个队伍做对第j道题目的概率。

dp[i][j][k]代表第i个队伍,对于前j道题目做对k道题目的概率。

所有队伍都做对1道及以上题目的概率bans*=(1-dp[i][m][0])//1-队伍做对0道题目的概率的乘积。

对于所有队伍都做对一道以及以上题目的概率的情况下:

至少有一个队伍做对n到题目的概率=所有队伍都做对1道题目的概率-所有队伍都做对小于n道题目的概率。

代码:

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INF_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
double p[1001][51];
double dp[1001][31][31];
int main()
{int m,t,n,i,j,k;while(scanf("%d%d%d",&m,&t,&n)&&(m||n||t)){for(i=1;i<=t;i++){for(j=1;j<=m;j++){scanf("%lf",&p[i][j]);}}for(i=1;i<=t;i++){dp[i][0][0]=1;for(j=1;j<=m;j++){dp[i][0][j]=0;}}for(i=1;i<=t;i++){for(j=1;j<=m;j++){dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]);for(k=1;k<=j;k++){dp[i][j][k]=dp[i][j-1][k]*(1-p[i][j])+dp[i][j-1][k-1]*p[i][j];}}}double bans;//所有人都做对1道及以上题目的概率bans=1;for(i=1;i<=t;i++){bans*=(1-dp[i][m][0]);}double ans;//至少有一个人做对n道题目的概率ans=1;for(i=1;i<=t;i++){double ks;ks=0;for(j=1;j<n;j++){ks+=dp[i][m][j];}ans*=ks;}ans=bans-ans;printf("%.3f\n",ans);}return 0;
}