动态规划

POJ1322总结

Chocolate

题目来源

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 

我的代码

这一题根本不需要滚动数组,因为当取出的巧克力数量是奇数时,所剩下的巧克力数量必须也是奇数,偶数同理。所以只需要开一个一维数组就行了。

另外精度要求是小数点后三位,我试了一下只要n大于c的100倍以上是肯定没影响的,看到网上的朋友们都是直接默认n最大值是1000(或1001),我很揪心,也不知道他们是这么一下子不约而同地找到这个值的。

#include<stdio.h>
#include<string.h>

int main()
{
	int c,m,n;
	while (scanf("%d",&c)==1&&c!=0)
	{
		scanf("%d%d",&n,&m);
		if (m>c)
		{
			printf("0.000\n");
			continue;
		} 
		if (m>n)
		{
			printf("0.000\n");
			continue;
		} 
		if (n%2!=m%2) 
		{
			printf("0.000\n");
			continue;
		}
		double dp[101]={0.0};
		dp[0]=1.0;
		if(n > 1001)  
            n = n % 2 ? 1001 : 1000;  

		for (int i=1;i<=n;i++)
		{
			if (i%2==0)
			{
				for (int j=0;j<=c;j=j+2) dp[j]=0;
				for (int j=1;j<=c;j=j+2)
				{
					if (j-1>=0) dp[j-1]+=dp[j]*(1.0*j)/c;
					if (j+1<=c) dp[j+1]+=dp[j]*(1.0*c-j)/c;
				}
			}
			else
			{
				for (int j=1;j<=c;j=j+2) dp[j]=0;
				for (int j=0;j<=c;j=j+2)
				{
					if (j-1>=0) dp[j-1]+=dp[j]*(1.0*j)/c;
					if (j+1<=c) dp[j+1]+=dp[j]*(1.0*c-j)/c;
				}
			}
		}
		printf("%.3f\n",dp[m]);
	}
	return 0;
}

反思

题目没有规定n的最小值不能是0,这就因为这当n是0时也是有结果的,我一开始写的是从1开始的。

发表评论