POJ 2151：Check the difficulty of problems 概率DP

#include<stdio.h>
#include<string.h>
double a[1001][31],dp[31][31];
int main()
{
	int m,t,n;
	double res1,res2,ans1,ans2;
	while(~scanf("%d%d%d",&m,&t,&n)&&(m||t||n))
	{
		for(int i=1;i<=t;++i)
		for(int j=1;j<=m;++j)
		scanf("%lf",&a[i][j]);
		ans1=ans2=1;
		for(int i=1;i<=t;++i)
		{
			res1=0,res2=0;
			dp[0][0]=1;
			for(int j=1;j<=m;++j)
			{
				dp[j][0]=dp[j-1][0]*(1-a[i][j]);
				for(int k=1;k<=j;++k)
				{
					dp[j][k]=dp[j-1][k-1]*a[i][j];
					if(j>k)dp[j][k]+=dp[j-1][k]*(1-a[i][j]);
					if(j==m)
					{
						res1+=dp[j][k];
						if(k<n)res2+=dp[j][k];
					}
				}
			}
			ans1*=res1;
			ans2*=res2;
		}
		printf("%.3f\n",ans1-ans2);
	}
}