记忆化就可以搞定,比赛里都没做出来,真的是态度有问题啊。。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double p[];
double dp[];
int flag[],n;
double po(double a,int k)
{
double b = 1.0;
while(k)
{
if(k&)
b = a*b;
a = a*a;
k = k/;
}
return b;
}
double dfs(int step)
{
int i;
if(flag[step])
return dp[step];
if(step == )
return p[];
double ans = p[],temp;
for(i = ;i < n;i ++)
{
temp = p[i];
temp *= po(dfs(step-),i);
ans += temp;
}
flag[step] = ;
return dp[step] = ans;
}
int main()
{
int t,cas = ,i,m,k;
double ans,temp;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&k,&m);
memset(flag,,sizeof(flag));
for(i = ;i < n;i ++)
scanf("%lf",&p[i]);
if(m == )
{
printf("Case #%d: %.7lf\n",cas++,0.0);
continue;
}
ans = ;
temp = dfs(m);
for(i = ;i < k;i ++)
ans *= temp;
printf("Case #%d: %.7lf\n",cas++,ans);
}
return ;
}