Chocolate_DP

时间:2022-09-02 16:24:09

Description

In 2100, ACM chocolate will be one of the favorite foods in the world.

"Green, orange, brown, red...", colorful sugar-coated shell maybe is the most attractive feature of ACM chocolate. How many colors have you ever seen? Nowadays, it's said that the ACM chooses from a palette of twenty-four colors to paint their delicious candy bits.

One day, Sandy played a game on a big package of ACM chocolates which contains five colors (green, orange, brown, red and yellow). Each time he took one chocolate from the package and placed it on the table. If there were two chocolates of the same color on the table, he ate both of them. He found a quite interesting thing that in most of the time there were always 2 or 3 chocolates on the table.

Now, here comes the problem, if there are C colors of ACM chocolates in the package (colors are distributed evenly), after N chocolates are taken from the package, what's the probability that there is exactly M chocolates on the table? Would you please write a program to figure it out?

Input

The input file for this problem contains several test cases, one per line.

For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000).

The input is terminated by a line containing a single zero.

Output

The output should be one real number per line, shows the probability for each case, round to three decimal places.

Sample Input

5 100 2

0

Sample Output

0.625 

【题意】给出c,n,m代表c种颜色的糖,从袋子里拿出n颗,放在桌子上,如果已经相同颜色,就把两颗都吃掉,问最后桌子剩m颗的概率

【思路】dp,dp[i][j]=dp[i-1][j-1]*(c-j+1)/c+dp[i-1][j+1]*(j+1)/c;

剪枝,m不可能大于n和c,并且n和m同奇同偶;

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
double dp[][];
int c,n,m;
while(cin>>c,c)
{
scanf("%d%d",&n,&m);
if(m>c||m>n||(n+m)&)
{
printf("0.000\n");
continue;
}
if(n>)//n很大时,误差可忽略不计
n=+(n&);
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++)
{
dp[i][]=dp[i-][]/c;
dp[i][c]=dp[i-][c-]/c;
for(int j=;j<c;j++)
{
dp[i][j]=dp[i-][j-]*(double)(c-j+)/c+dp[i-][j+]*(double)(j+)/c;
}
}
printf("%.3f\n",dp[n][m]);
}
return ;
}

Chocolate_DP的更多相关文章

    随机推荐

    1. 快刀斩乱麻之 Katana

      Katana-武士刀,寓意:快.准.狠! 按照常规,我们一般编写的 ASP.NET 应用程序会部署在 IIS 上(有点傻的描述),在 ASP.NET 应用程序中,我们会大量使用 HttpContext ...

    2. XML的约束&lpar;dtd&rpar;

      DTD(Document Type Definition),文档类型定义,DTD文件应使用UTF-8或Unicode   1.XML中有多少个元素,就在dtd文件中写几个 <!ELEMENT&g ...

    3. 实战FFmpeg编译支持arm64&lpar;转&rpar;

      App store要求上架的app必须支持arm64.而手中的ffmpeg还不支持arm64, 百度下ffmpeg支持arm64方法,网上有很多资料.其中一篇是使用脚本自动编译实现的.本文就是使用它的 ...

    4. 转:说说JSON和JSONP,也许你会豁然开朗,含jQuery用例

      说到AJAX就会不可避免的面临两个问题,第一个是AJAX以何种格式来交换数据?第二个是跨域的需求如何解决?这两个问题目前都有不同的解决方案,比如数据可以用自定义字符串或者用XML来描述,跨域可以通过服 ...

    5. 搭建lamp环境Q&amp&semi;A

      Q1:no acceptable C compiler found in $PATH A:yum -y install gcc Q2:红帽没有注册,无法使用yum A:vim /etc/yum.rep ...

    6. windows上安装ubuntukylin16&period;04并且在ubuntukylin上安装jdk

      1.安装ubuntukylin16.04 教程链接:http://jingyan.baidu.com/article/f71d60379824041ab641d19d.html 我是完全按照这个教程来 ...

    7. 提高java编程质量 - (一)易变业务使用脚本语言编写

      脚本语言的3大特征: 1.灵活:脚本语言一般是动态类型,可以不声明变量类型直接使用,也可以在运行期改变类型:2.便捷:脚本语言是解释性语言,在运行期变更非常方便,而不用重启服务3.简单:脚本语言语法比 ...

    8. 28&period;Implement strStr&lpar;&rpar;【leetcod】

      Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle ...

    9. 推举算法 AdaBoost 哥德尔奖 Godel Prize

      推举算法 AdaBoost  2003年理论计算机科学界最高奖 哥德尔奖 Godel Prize

    10. Ubuntu 安装google chrome

      sudo apt-get install google-chrome-stable /usr/bin/google-chrome-stable

    相关文章