UVA 11021 C

记忆化就可以搞定，比赛里都没做出来，真的是态度有问题啊。。。
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 double p[1001];
 7 double dp[1001];
 8 int flag[1001],n;
 9 double po(double a,int k)
10 {
11     double b = 1.0;
12     while(k)
13     {
14         if(k&1)
15         b = a*b;
16         a = a*a;
17         k = k/2;
18     }
19     return b;
20 }
21 double dfs(int step)
22 {
23     int i;
24     if(flag[step])
25     return dp[step];
26     if(step == 1)
27     return p[0];
28     double ans = p[0],temp;
29     for(i = 1;i < n;i ++)
30     {
31         temp = p[i];
32         temp *= po(dfs(step-1),i);
33         ans += temp;
34     }
35     flag[step] = 1;
36     return dp[step] = ans;
37 }
38 int main()
39 {
40     int t,cas = 1,i,m,k;
41     double ans,temp;
42     scanf("%d",&t);
43     while(t--)
44     {
45         scanf("%d%d%d",&n,&k,&m);
46         memset(flag,0,sizeof(flag));
47         for(i = 0;i < n;i ++)
48         scanf("%lf",&p[i]);
49         if(m == 0)
50         {
51             printf("Case #%d: %.7lf
",cas++,0.0);
52             continue;
53         }
54         ans = 1;
55         temp = dfs(m);
56         for(i = 0;i < k;i ++)
57         ans *= temp;
58         printf("Case #%d: %.7lf
",cas++,ans);
59     }
60     return 0;
61 }