首页 > 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. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  2. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  3. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  4. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  5. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  6. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  7. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  8. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  9. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  10. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  11. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  12. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

  13. 对啊,你都承认了这是废话了。换句话说,买房不长期持有,短期卖出才叫炒房(短期指5年以内,国家政策上都把满五唯一作为正常出售看待,低于5年的提高税率)你看看你说的“炒房者”有几个是5年以内就卖出了的?

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

  15. 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!

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