【HDOJ】1204 糖果大战

题目本身不难。类似于dp。f(i)表示手中现有i颗糖果赢的概率，则下一局赢的概率是p(1-q)，下一局输的概率是q(1-p)，下一句平手的概率是1-p(1-q)-q(1-p)，平手包括两人均答对或答错。那么可推导状态转移方程：
f(i) = p(1-q)f(i-1) + q(1-p)f(i+1) + [ 1-p(1-q)-q(1-p) ]f(i)
归并相同项可以得到等比数列，p(1-q)(f(i) - f(i-1)) = q(1-p)(f(i+1) - f(i))。设定比例系数，并利用等比数列求和公式可求。其中需要注意的是，f(0)=0，f(n+m)=1，因为手中若已经有n+m颗糖果，则已经获得全部胜利。我们需要求的是f(n)的概率是多少。除了考虑n或m为0的情况，还有p或q为1/0的情况，还必须考虑等比系数为1的情况，当等比系数为1无法用等比求和公式时，则证明二者答对的概率相等，此时应当考虑两者的糖果数目（概率论等概率）。等比为1，很容易想不到，wa了很多次。

 #include <stdio.h>

 #include <math.h>

 int main() {

     int m, n;

     double p, q, winp, tmp;

     while (scanf("%d%d%lf%lf", &n, &m, &p, &q) != EOF) {

         if (n == )

             printf("0.00\n");

         else if (m == )

             printf("1.00\n");

         else if (p== || q==)

             printf("0.00\n");

         else if (p== || q==)

             printf("1.00\n");

         else if (p == q) {  // k==0

             winp = 1.0*n/(m+n);

             printf("%.2lf\n", winp);

         } else {

             tmp = q*(1.0-p) / (p*(1.0-q));

             winp = (1.0-pow(tmp, n)) / (1.0-pow(tmp,n+m));

             printf("%.2lf\n", winp);

         }

     }

     return ;

 }

巴特西

【HDOJ】1204 糖果大战

最新文章

热门文章