Uva10207 The Unreal Tournament

发布时间:2016-12-19 11:58:21编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Uva10207 The Unreal Tournament ",主要涉及到Uva10207 The Unreal Tournament 方面的内容,对于Uva10207 The Unreal Tournament 感兴趣的同学可以参考一下。

题目链接戳这里

首先递归调用函数次数其实是可以预处理出来的,但是这里我们介绍一个更屌的做法。
\(F(i,j)\)为求解\(P(i,j)\)所遍历的节点数目,则有\[F(0,j)=F(i,0)=0\]
\[F(i,j)=F(i-1,j)+F(i,j-1)+2\]
我们观察一下,发现这个式子与组合恒等式\[\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}\]
于是我们可以令\(G(i,j)=F(i,j)+2\),则有\[G(i,j) = G(i-1,j)+G(i,j-1)\]
再通过待定系数便可以得到\[F(i,j)=2\binom{i+j}{i}-1\]
下面考虑\(P(i,j)\)的求法,我们可以枚举起始点\((0,a)\)(就是枚举递归边界),则这个点对答案的贡献即为\[\binom{i+j-a-1}{j-a}p^{i}(1-p)^{j-a}\]
这个可以画一个格点图来考虑。

那么算法我们分析完了,接下来就是这道题最蛋痛的地方了——高精度。我开始C++为了不写除法特意采用了质因子合并的算法,并且还保证了复杂度。但是,玩玩没想到算\(P(i,j)\)的时候double的精度不够,可能要用取对数的思想,但我不想想了。于是便将目光转向java,BigDecimal类精度绝对够了。下面就是我的代码:

import java.math.*;import java.util.*;public class Main{    static final int num = 2010;    static BigInteger C[][] = new BigInteger[num][num];    public static void main(String args[])    {        for (int i = 0;i < num;++i) for (int j = 0;j < num;++j) C[i][j] = BigInteger.ZERO;        for (int i = 0;i < num;++i)        {            C[i][0] = BigInteger.ONE;            for (int j = 1;j <= i;++j) C[i][j] = C[i-1][j-1].add(C[i-1][j]);        }        Scanner cin = new Scanner(System.in); BigDecimal P,Q; int Case = 0;        while (true)        {            P = cin.nextBigDecimal(); Q = (BigDecimal.valueOf(1)).subtract(P);            int N = cin.nextInt(); if (N == 0) break;            if (Case++ > 0) System.out.println("");            while ((N--) > 0)            {                int a = cin.nextInt(),b = cin.nextInt();                if (a <= 0&&b <= 0) System.out.println("-1.00000\n0");                else if (a < 0||b < 0) System.out.println("-1.00000\n0");                else if (a > 1000||b > 1000) System.out.println("-1.00000\n0");                else                {                    BigDecimal sum = new BigDecimal(0);                    if (a == 0) sum = BigDecimal.valueOf(1);                    else for (int i = 1;i <= b;++i) sum = sum.add(new BigDecimal(C[a+b-i-1][a-1]).multiply(P.pow(a).multiply(Q.pow(b-i))));                    System.out.format("%.5f\n",sum);                    System.out.println(C[a+b][a].multiply(BigInteger.valueOf(2)).subtract(BigInteger.valueOf(2)));                }


上一篇:spring MVC配置详解(转)
下一篇:Mac Pro 日历增强工具 Itsycal

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款