4766271_wa.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
float p[1005][35];
float mem[1005][35][35];
bool used[1005][35][35];
int m,t,n;
float get(int n,int s,int now)
{
	float re;
	if(used[now][s][n]) return mem[now][s][n];
	if((m-s+1)==n) 
	{
		int i;
		re=1.0;
		for(i=s;i<=m;i++) re*=p[now][i];
	}
	else
	if(n==0)
	{
		int i;
		re=1.0;
		for(i=s;i<=m;i++) re*=1.0-p[now][i];
	}
	else
	{
		re=p[now][s]*get(n-1,s+1,now)+(1.0-p[now][s])*get(n,s+1,now);
	}
	mem[now][s][n]=re;
	used[now][s][n]=true;
	return re;
}
int main()
{
	while(1)
	{
		cin>>m>>t>>n;
		memset(used,false,sizeof(used));
		if(!m&&!t&&!n) return 0;
		int i,j;
		for(i=1;i<=t;i++)
			for(j=1;j<=m;j++)
				cin>>p[i][j];
		float slove=1.0;
		float all_slove_under_n=1.0;
		for(i=1;i<=t;i++)
		{
			float re=get(0,1,i);
			slove*=(1.0-re);
		}
		for(i=1;i<=t;i++)
		{
			float slove_under_n=0.0;
			for(j=1;j<n;j++)
				slove_under_n+=get(j,1,i);
			all_slove_under_n*=slove_under_n;
		}
		float result;
		result=slove*(1.0-all_slove_under_n);//-(1.0-slove);
		printf("%.3lf\n",result);
	}
}