poj 2151 Check the difficulty of problems dp - c++编程基础

概率dp的题目，不过我的做法可能比较不一样，先计算出每个人答对1~n-1,n~m道题目的概率。

然后dp[i][0] 表示前i个人，有一个人至少答对n道题，并且每个人至少一个题目的概率。

dp[i][1] 表示前i个人，每个人至少答对一道题目的概率。

状态转移就很明显了。

#include   
#include   
#include   
using namespace std;  
const int maxn=1e3+9;  
double cha[111][111];  
double dp[maxn][2];  
double p[maxn];  
int n,m,t;  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    while(scanf("%d%d%d",&m,&t,&n),t)  
    {  
        memset(dp,0,sizeof(dp));  
        dp[0][0]=1;  
        for(int k=1;k<=t;k++)  
        {  
            for(int j=1;j<=m;j++)  
            scanf("%lf",&p[j]);  
            memset(cha,0,sizeof(cha));  
            cha[0][0]=1;  
            for(int i=1;i<=m;i++)  
            for(int j=0;j<=i;j++)  
            {  
                if(j)  
                cha[i][j]=cha[i-1][j-1]*p[i]+cha[i-1][j]*(1-p[i]);  
                else  
                cha[i][j]=cha[i-1][j]*(1-p[i]);  
            }  
            double p1=0,p2=0;  
            for(int i=1;i