文档介绍：00748022李井1322解题报告题目大意ACM牌巧克力共有C中不同颜色的品种。一天,Sandy进行了如下游戏:从一个装满巧克力的袋子(袋中的不同颜色的巧克力是同样多的,且假定巧克力数目足够多),一个一个拿出巧克力放于桌上,如拿出的巧克力与桌上某一个巧克力颜色相同,那么Sandy则将两块全部吃掉。现要求从袋中拿出了N块巧克力后,桌面上还剩余M块巧克力的概率。INPUT&OUTPUT输入:多CASE,每一行分别是三个数据,表示C,N,M,以单个0行作为结束输出:对每一组数据输出一个数,即为所求概率特别说明:结果只须保留3位小数数据规模:C<=100N,M<= ,从袋中拿出100块巧克力后,。因为我们很难手算出这个概率值。再看一个更为简单的例子。一个更为简单的例子C=3 N=4 M=2P=(N,M)表示拿出N块巧克力后,桌上还剩M块巧克力的概率我们可以得到下面的结论 (1)P(N,M)=0当N+M为奇数 (2)P(N,M)=P(N-1,M-1)*P1+P(N-1,M+1)*P2其中P1=(C-M+1)/C,P2=(M+1)/C一个思路这样我们显然就得到了一个朴素的思路,用递归来求解。递推式即为上式补充边界条件:(1)当M=0,上式化为P(N,M)=P(N-1,M+1)*P2(2)当M=C,上式化为P(N,M)=P(N-1,M-1)*P1(3)当N=1,出口条件为P(1,M)=1,M=10,M!=1TIMELIMITEXCEEDED!P(I,J)结点很可能被走过多便,造成冗余,影响效率。解决方案:递归转动归动态规划遇到的问题回顾一下数据规模C<=100N,M<=1000000显然我们无法开出1000000*1000000的数组也就是说,我们无法对如此大规模的数据进行动态规划找规律