ZOJ3329（数学推导+期望递推）

要点：

1.期望的套路，要求n以上的期望，则设dp[i]为i分距离终点的期望步数，则终点dp值为0，答案是dp[0]。

2.此题主要在于数学推导，一方面是要写出dp[i] = 什么，虽然一大串但是思维上并不难；然后就是一种解方程的方法，因为都跟dp[0]有关，且dp[0]是个确定的常数，所以设dp[i] = A[i] * dp[0] + B[i]，带入上面那一串解出A[i]、B[i]，发现是个递推式，于是递推求出A[i]B[i]即可得到dp[0] = B[0] / (1 - A[0])。推荐邝斌聚聚博客。

式子出来了，代码就好写了：

 int T, n, K1, K2, K3, a, b, c;

 db p[];

 db A[], B[];

 void GetPk() {

     p[] = 1.0 / K1 / K2 / K3;

     rep(i, , K1)    rep(j, , K2)    rep(k, , K3) {

         if (i == a && j == b && k == c)    continue;

         p[i + j + k] += p[];

     }

 }

 void GetAB() {

     irep(i, n, ) {

         A[i] = p[];

         B[i] = ;

         rep(j, , K1 + K2 + K3) {

             A[i] += A[i + j] * p[j];

             B[i] += B[i + j] * p[j];

         }

     }

 }

 int main() {

     ios_base::sync_with_stdio(false);

     cin.tie();

     for (cin >> T; T; T--) {

         init(A, ), init(B, ), init(p, );

         cin >> n >> K1 >> K2 >> K3 >> a >> b >> c;

         GetPk(), GetAB();

         cout << fixed << setprecision() << B[] / ( - A[]) << endl;

     }

     return ;

 }

巴特西

ZOJ3329（数学推导+期望递推）

最新文章

热门文章