鸡蛋掉落问题的动态规划解法

#include<bits/stdc++.h>
using namespace std;
int f[12][1100];
/*
f[i][j]表示拿 i 个蛋测试 j 层楼需要的最少次数 
枚举k for(1~j) 表示最后测试的楼层 
此时有两种情况 
1.这一层(k)蛋碎了，则 k~j 楼不用测试，等同于我们用 i-1 个蛋来测试 k-1 层楼 
2.这一层(k)蛋没碎，则 1~k 楼不用测试，等同于我们用 i   个蛋来测试 j-k 层楼 
我们要把这两种情况下最多的步数作为答案 
所以dp转移方程为 f[i][j]=max(f[i-1][k-1],f[i-1][j-k])+1; 
*/
int main()
{
	memset(f,63,sizeof(f));
	for(int i=1;i<=10;i++)f[i][0]=0;//0层楼特判 
	for(int i=1;i<=10;i++)f[i][1]=1;//1层楼特判 
	for(int i=1;i<=1000;i++)f[1][i]=i;//1个鸡蛋特判 
	for(int i=2;i<=10;i++)
	{
		for(int j=2;j<=1000;j++)
		{
			for(int k=1;k<=j;k++)//k是最后的测试楼层 
			{
				f[i][j]=min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1);
				/*
				为什么有个min、max 
				max是最坏情况，因为你特倒霉，实际测试会朝最坏情况的方向走 
				min是什么？ 
				你用 i 个蛋，测 j 层楼，最后一次实验了，你要选一层楼对吧 
				你有选择权了！肯定选最好的方案啦 
				想想看(举栗子) 
				一个 SB 免费选一张10元、一张50元、一张100元，他或许只拿了10元的 
				一个聪明人免费选一张1元、一张5元、一张10元， 要拿就全拿呗 
				10<16
				看！即使聪明人的处境糟糕，他也可以通过选择策略来谋取幸福生活 
				那你dp就取最小值呗，有机会不把握，zz 
				*/
			}
		}
	}
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		if(n>10)n=10;
		/*
		因为你鸡蛋太多，但楼层有限(k<=1000) 
		所以你可以不考虑鸡蛋的损耗 
		大大方方的丢鸡蛋就好，别怂 
		所以你每次都可以二分法来判定一半的楼层 
		2的10次方>1000
		所以鸡蛋多了也没用，还不如拿去XX 
		*/
		printf("%d\n",f[n][k]);
	}
	return 0;
}