题意：一个人在迷宫里面，这个人有f的攻击力。他一共有n条通道可供随机选择，每次等概率随机选择一条。对每条通道i有参数c[i]。选择通道k后，若f > c[k]，则花费时间t[k]逃出迷宫，否则花费一天，攻击力f增加c[k]，且一天之后继续选择通道。求逃出去所花费的天数的期望。其中t[k] = (int)((1+√5) * c[k]*c[k] / 2)。

解法：概率DP加记忆化写法。设d[i]表示当攻击力为i逃出去所花费的天数的期望，遍历每个通道j，若i > c[j]则d[i] += t[j] / n，否则d[i] += (1 + d[i+c[j]]) / n。

tag:概率DP，记忆化

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-11-16 19:38 4  * File Name: DP-ZOJ-3640.cpp 5  */ 6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 11 using namespace std;12 13 int n, f;14 int c[10005];15 double x;16 17 double DP(int f)18 {19     double ret = 0.0;20     for (int i = 1; i <= n; ++ i){21         if (f > c[i]) ret += (int)(x * c[i] * c[i]);22         else ret += 1 + DP(f+c[i]);23     }24     ret /= (double)n;25     return ret;26 }27 28 int main()29 {30     x = (1 + sqrt(5)) / (double)2;31     while (scanf ("%d%d", &n, &f) != EOF && n){32         for (int i = 1; i <= n; ++ i)33             scanf ("%d", &c[i]);34         printf ("%.3f\n", DP(f));35     }36     return 0;37 }