【gzoj】鸡蛋的硬度【基础概率DP】

题意

给出楼层高n，鸡蛋个数m，每个鸡蛋有相同的硬度x，即在x+1层以上往下扔就会烂，反之不烂，没烂鸡蛋就能继续使用，问在最坏情况下使用最优策略所需要的扔鸡蛋次数。

分析

这道题如果直接用二分或者三分是达不到最优的。

所以从问题出发，考虑DP做法，一般来讲是用递归的思想看问题，然后一个一个枚举正推就是转移方程了。

设 $f[i][j]$ 为 $i$ 层楼，$j$ 个鸡蛋在最坏情况下的最优解。对于每一个 $j$，可以这样想：取出一个来在第 $k$ 层扔，就变成 $j-1$ 个和这一个的问题了，对于这一个来讲，扔下去有两种结果，烂或者不烂。如果烂了，证明硬度在 $k$ 之下，所以层数变成了 $k-1$，鸡蛋数变成了 $j-1$，反之则层数变成了 $i-k$，鸡蛋数还是 $j$ 。这两种状态分别是 $f[k-1][j-1]$ 和 $f[i-k][j]$。其中这个k是要在1~i 之间暴力枚举的。因为这两种都是“情况”，而我们要最坏情况，当然要取max啦，然后再与 $f[i][j]$ 比较，因为这是我们选择的策略，当然要取min啦。

转移方程：$f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);$

上代码

#include
#include
#include
using namespace std;

int n,m,f[110][11];

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				f[i][j]=i;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=2;j<=m;j++)//至少两个开始转移，一个的已经处理过，不然会越界 
			{
				for(int k=1;k<=i;k++)
				{
					f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
				}
			}
		}
		cout<<f[n][m]<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32