首页 > ACM题库 > HDU-杭电 > HDU 3076-ssworld VS DDD-动态规划-[解题报告]HOJ
2014
03-01

HDU 3076-ssworld VS DDD-动态规划-[解题报告]HOJ

ssworld VS DDD

问题描述 :

One day, sssworld and DDD play games together, but there are some special rules in this games.
They both have their own HP. Each round they dice respectively and get the points P1 and P2 (1 <= P1, P2 <= 6). Small number who, whose HP to reduce 1, the same points will remain unchanged. If one of them becomes 0 HP, he loses.
As a result of technical differences between the two, each person has different probability of throwing 1, 2, 3, 4, 5, 6. So we couldn’t predict who the final winner.

输入:

There are multiple test cases.
For each case, the first line are two integer HP1, HP2 (1 <= HP1, HP2 <= 2000), said the first player sssworld’s HP and the second player DDD’s HP.
The next two lines each have six floating-point numbers per line. The jth number on the ith line means the the probability of the ith player gets point j. The input data ensures that the game always has an end.

输出:

There are multiple test cases.
For each case, the first line are two integer HP1, HP2 (1 <= HP1, HP2 <= 2000), said the first player sssworld’s HP and the second player DDD’s HP.
The next two lines each have six floating-point numbers per line. The jth number on the ith line means the the probability of the ith player gets point j. The input data ensures that the game always has an end.

样例输入:

5 5
1.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 1.000
5 5
0.000 0.000 0.000 0.000 0.000 1.000
1.000 0.000 0.000 0.000 0.000 0.000

样例输出:

0.000000
1.000000

题意:

 A,B掷骰子,对于每一次点数大者胜,平为和,A先胜了m次A赢,B先胜了n次B赢。

题解:

 先将平局情况处理出来,让他们一定要分出胜负,对于每一次p1表示A赢,p2表示B赢,p=1-p1-p2表示平局,所以在不死不休的情况下,A赢的概率为p1+p*p1+p^2*p1+…p^n*p1,n->无穷,即a_win=q1/(1-p);b_win=q2/(1-p);

然后在他们一定会分出胜负的情况下就可以dp了:

   dp[i][j]=dp[i][j-1]*a_win+dp[i-1][j]*b_win;

dp[i][j]表示A胜j次,B胜i次的概率。

#include<iostream>
using namespace std;
#define MAXN 2005
double dp[MAXN][MAXN];
double a[7],b[7];
double a_win,b_win;    
double ans;
int main()
{
    int n,m,i,j;
    double p,p1,p2;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
       for(i=1;i<=6;i++)
           scanf("%lf",&a[i]);
       for(i=1;i<=6;i++)
           scanf("%lf",&b[i]);
       a_win=0;
       for(i=2;i<=6;i++)
       {
           for(j=1;j<=i-1;j++)
               a_win+=a[i]*b[j];
       }
       b_win=0;
       for(i=2;i<=6;i++)
       {
           for(j=1;j<=i-1;j++)
               b_win+=b[i]*a[j];
       }
       p1=a_win;p2=b_win;p=1-a_win-b_win;
       if (p==1) {a_win=0;b_win=0;}
       else
       {
           a_win=p1/(1-p);
           b_win=p2/(1-p);
       }
       for(i=0;i<=n;i++)
           for(j=0;j<=m;j++)
               dp[i][j]=0;
     // cout<<a_win<<' '<<b_win<<endl;
     dp[0][0]=1;
      for(j=0;j<=m-1;j++)
         for(i=0;i<=n;i++)       
               if (i+j!=0)
           {
                   dp[i][j]=0;
                   if (j>0)
               dp[i][j]+=dp[i][j-1]*a_win;
                   if (i>0)
               dp[i][j]+=dp[i-1][j]*b_win;
           }
       ans=0;
       for(i=0;i<=n-1;i++)
           ans+=dp[i][m-1]*a_win;
     if (ans>1) ans=1;
       printf("%.6lf/n",ans);
    }
}

参考:http://blog.csdn.net/swordholy/article/details/5924212


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。