HDU 3076 ssworld VS DDD 概率DP

设计模式 前端之家
前端之家收集整理的这篇文章主要介绍了HDU 3076 ssworld VS DDD 概率DP，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
网址：http://acm.hdu.edu.cn/showproblem.PHP?pid=3076
题目：<h1 style="color: rgb(26,92,200); text-align: center; font-family: 'Times New Roman';">ssworld VS DDD</h1><span style="font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center;"><strong><span style="font-family: Arial; font-size: 12px; color: green;">Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1989Accepted Submission(s): 383
</span></strong></span><br style="font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center;" /><br style="font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center;" /><div class="panel_title" align="left" style="height: 38px; padding: 0px 14px; color: rgb(124,169,237); font-size: 18px; font-family: Arial; font-weight: bold; background: url(http://acm.hdu.edu.cn/images/panel-title.png) 0% 100% no-repeat transparent;">Problem Description</div><div class="panel_content" style="height: auto; margin: 0px; padding: 0px 20px; font-size: 14px; font-family: 'Times New Roman'; background: url(http://acm.hdu.edu.cn/images/panel-content.png) repeat-y;">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.

</div><div class="panel_bottom" style="height: auto; margin: 0px; font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center; background: url(http://acm.hdu.edu.cn/images/panel-bottom.png) 0% 0% no-repeat;"></div><br style="font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center;" /><div class="panel_title" align="left" style="height: 38px; padding: 0px 14px; color: rgb(124,237); font-size: 18px; font-family: Arial; font-weight: bold; background: url(http://acm.hdu.edu.cn/images/panel-title.png) 0% 100% no-repeat transparent;">Input</div><div class="panel_content" style="height: auto; margin: 0px; padding: 0px 20px; font-size: 14px; font-family: 'Times New Roman'; background: url(http://acm.hdu.edu.cn/images/panel-content.png) repeat-y;">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.
</div><div class="panel_bottom" style="height: auto; margin: 0px; font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center; background: url(http://acm.hdu.edu.cn/images/panel-bottom.png) 0% 0% no-repeat;"></div><br style="font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center;" /><div class="panel_title" align="left" style="height: 38px; padding: 0px 14px; color: rgb(124,237); font-size: 18px; font-family: Arial; font-weight: bold; background: url(http://acm.hdu.edu.cn/images/panel-title.png) 0% 100% no-repeat transparent;">Output</div><div class="panel_content" style="height: auto; margin: 0px; padding: 0px 20px; font-size: 14px; font-family: 'Times New Roman'; background: url(http://acm.hdu.edu.cn/images/panel-content.png) repeat-y;">One float with six digits after point,indicate the probability sssworld won the game.</div><div class="panel_bottom" style="height: auto; margin: 0px; font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center; background: url(http://acm.hdu.edu.cn/images/panel-bottom.png) 0% 0% no-repeat;"></div><br style="font-family: 'Times New Roman';font-size:14px; text-align: -webkit-center;" /><div class="panel_title" align="left" style="height: 38px; padding: 0px 14px; color: rgb(124,237); font-size: 18px; font-family: Arial; font-weight: bold; background: url(http://acm.hdu.edu.cn/images/panel-title.png) 0% 100% no-repeat transparent;">Sample Input</div><div class="panel_content" style="height: auto; margin: 0px; padding: 0px 20px; font-size: 14px; font-family: 'Times New Roman'; background: url(http://acm.hdu.edu.cn/images/panel-content.png) repeat-y;"><pre style="word-wrap: break-word; white-space: pre-wrap; margin-top: 0px; margin-bottom: 0px;"><div style="font-family: 'Courier New',Courier,monospace;">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</div>

@H_404_9@ Sample Output 
  
  

   
   0.000000
1.000000

@H_404_9@ Source
2009 Multi-University Training Contest 17 - Host by NUDT 
 

 

题意A、B两人扔色子，分别给出他们初始的分数H1和H2，再给出它们扔 1- 6的概率，扔出分数低的人会失去一分，平局则继续扔，最先变为0的人就输，比赛终止。
 

当一个人扔出的分数不另一个人小时，他就会输，所以利用两层循环找出A，B各自获胜的概率wa，wb，见代码。若果出现平局，他们会继续扔，那么A,B各自获胜的概率依然是
 

wa，wb，一直循环下去；所以每一句A、B获胜的概率就是s=wa+wb;  wa=wa/s;(A的）  wb=wb/s;（B的）；
 

然后用dp[i][j]表示A分数为i，b分数为j是A获胜的概率，因为一局只有A胜或B胜2总情况，所以dp[i][j]=dp[i-1][j]*wb+dp[i][j-1]*wa;初始化B的分数为0时，dp[i][0]=1;
 

又dp[0][j]=0;
 

最后题目内存限制采用滚动数组；最坑的是目数据H1，H2是反的，一直wrong到上网看题解，要反过来才行。
 

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include<cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <string>
#include <cctype>
#include <map>
#include <vector>
#include<stack>
#include<cmath>
#include<queue>

#define pb push_back
#define mp make_pair
#define mem(a) memset(a,sizeof(a))
#define fore(i,s,t) for(int i=s;i<t;i++)
#define  LL __int64

using namespace std;

const int maxn = 2100,inf = ~(1 << 31),mod = 258280327;
const double eps = 1e-7,pi = acos(-1.0);
double dp[maxn],adp[maxn],pa[7],pb[7],wa,wb;
int main(void)
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        mem(dp);
        mem(adp);
        wa=wb=0;
        for(int i=1; i<=6; i++)scanf("%lf",&pa[i]);
        for(int i=1; i<=6; i++)scanf("%lf",&pb[i]);

        for(int i=2; i<=6; i++)
            for(int j=1; j<i; j++)
            {
                wa+=pa[i]*pb[j];
                wb+=pb[i]*pa[j];
            }
        double s=wa+wb;
        wa/=s;
        wb/=s;

        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
                dp[j]=adp[j]*wb+(j==1?1:dp[j-1])*wa;
            for(int j=1; j<=n; j++) adp[j]=dp[j];
        }
        printf("%.6lf\n",dp[n]);
    }
    return 0;

}
/*

0.200 0.300 0.200 0.000 0.000 0.300
0.000 0.000 0.500 0.000 0.000 0.500
2 1
0.200 0.300 0.200 0.000 0.000 0.300
0.000 0.000 0.500 0.000 0.000 0.500
1 2
0.000 0.000 0.500 0.000 0.000 0.500
0.200 0.300 0.200 0.000 0.000 0.300
1 1000
0.000 0.000 0.000 0.000 0.000 1.000
1.000 0.000 0.000 0.000 0.000 0.000

*/


      

      
                 
              

            

          

          
          
          

            

              




            

          


          

            

              

                  
    
猜你在找的设计模式相关文章



                                    
适配器模式-让不兼容的接口得以适配

                                
适配器模式将一个类的接口转换成客户期望的另一个接口，使得原本接口不兼容的类可以相互合...

                                
                                
                            



                                    
策略模式-定义一个算法族

                                
策略模式定义了一系列算法族，并封装在类中，它们之间可以互相替换，此模式让算法的变化独...

                                
                                
                            



                                    
设计模式之高质量代码

                                
设计模式讲的是如何编写可扩展、可维护、可读的高质量代码，它是针对软件开发中经常遇到的...

                                
                                
                            



                                    
模板方法模式-封装一套算法流程

                                
模板方法模式在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类中，使得子类可以在...

                                
                                
                            



                                    
迭代器模式-统一集合的遍历方式

                                
迭代器模式提供了一种方法，用于遍历集合对象中的元素，而又不暴露其内部的细节。

                                
                                
                            







                                    
单例模式的五种实现方式及优缺点

                                
单例模式（Singleton Design Pattern）保证一个类只能有一个实例，并提供一个全局访问点。

                                
                                
                            



                                    
组合模式-统一的处理个别对象与组合对象

                                
组合模式可以将对象组合成树形结构来表示“整体-部分”的层次结构，使得客户可以用一致的方...

                                
                                
                            



                                    
装饰者模式-动态的包装原有对象的行为

                                
装饰者模式能够更灵活的，动态的给对象添加其它功能，而不需要修改任何现有的底层代码。

                                
                                
                            



                                    
观察者模式-将消息通知给观察者

                                
观察者模式（Observer Design Pattern）定义了对象之间的一对多依赖，当对象状态改变的时候...

                                
                                
                            



                                    
代理模式-访问对象的代理而非其本身

                                
代理模式为对象提供一个代理，来控制对该对象的访问。代理模式在不改变原始类代码的情况下...

                                
                                
                            







            

          

        

        
        
        
        

          
          

            

              

                
                
算法设计模式多媒体技术正则表达式ElasticsearchFlinkHadoopIDE

                

              

            

          

          
         
          

            

              
 



              

            

          

          
          
          
          

            

              

                
                
              

            

          

          


          
          

            

              

                
                
受约束摘*day25Java常用类库置信lamda留存持续录入年后正则表达式303.17regularexpre匹多模适20130322基础理论pathmunge涵义reectok需要转义的特资源分享validationex简明魔法里弄形如源码实现完备actionscript