题解：
对于期望值，一般定义的Ex都是表示离目标状态还需要的代价
所以这里定义E[i]表示当前状态为i离结束还需要代价的期望值，那答案就是E[0]。
对于期望类问题，一般解法是列出方程式，若状态之间存在环，则可采用高斯消元解方程组，也可想办法消环；反之，则可直接递推来求出目标状态。
对于该题：
E[x] = 0 (x>n)；
E[i] = ∑Pk*E[i+k] + P0*E[0] + 1；
设 E[i] = a[i]*E[0] + b[i];
联合上面的式子可消去E[i+k]，可得E[i] = ( ∑Pk*a[i+k] + P0 )*E[0] + ∑Pk*b[i+k] + 1;
可得出：
a[i] = ∑Pk*a[i+k] + P0;
b[i] = ∑Pk*b[i+k] + 1;
接下来可求出ai和bi，最后得出E[0] = b[0]/(1-a[0]);
View Code
1 /* 2 Author:Zhaofa Fang 3 PROB:zoj 3329 4 Lang:C++ 5 */ 6 #include <cstdio> 7 #include <cstdlib> 8 #include <iostream> 9 #include <cmath> 10 #include <cstring> 11 #include <algorithm> 12 #include <string> 13 #include <utility> 14 #include <vector> 15 #include <queue> 16 #include <stack> 17 #include <map> 18 #include <set> 19 using namespace std; 20 21 typedef long long ll; 22 const int INF = 2147483647; 23 24 double e[550]; 25 double p[550]; 26 double x[550]; 27 int a,b,c; 28 void init(double k1,double k2,double k3) 29 { 30 for(int i=0;i<550;i++)p[i]=e[i]=x[i]=0; 31 for(int i=1;i<=(int)k1;i++) 32 { 33 for(int j=1;j<=(int)k2;j++) 34 { 35 for(int k=1;k<=(int)k3;k++) 36 { 37 if(a!=i || b != j || c != k) 38 p[i+j+k]+= 1.0/(k1*k2*k3); 39 } 40 } 41 } 42 } 43 int main() 44 { 45 #ifndef ONLINE_JUDGE 46 freopen("in","r",stdin); 47 #endif 48 int T; 49 cin>>T; 50 while(T--) 51 { 52 int n; 53 double k1,k2,k3; 54 scanf("%d%lf%lf%lf",&n,&k1,&k2,&k3); 55 scanf("%d%d%d",&a,&b,&c); 56 init(k1,k2,k3); 57 for(int i=n;i>=0;i--) 58 { 59 e[i] = 1/(k1*k2*k3); 60 x[i] = 1.0; 61 for(int j=3;j<=(int)(k1+k2+k3);j++) 62 { 63 e[i] += p[j]*e[i+j]; 64 x[i] += p[j]*x[i+j]; 65 } 66 } 67 printf("%.15f\n",x[0]/(1-e[0])); 68 } 69 return 0; 70 }