LGU67496 小$s$的玻璃弹珠

题意

在一幢(m)层建筑你将获得(n)个一样的鸡蛋，从高于(x)的楼层落下的鸡蛋都会碎。如果一个蛋碎了，你就不能再把它掉下去。
你的目标是确切地知道(x)的值。问至少要扔几次才能确定。
(1 leq n leq 100,1 leq mleq 10000)

思路

(f[move][i])表示移动(move)次,(i)个鸡蛋,最优解的最坏条件下可以检测的楼层数(x)

若(f[move-1][i-1]=x_0,f[move-1][i]=x_1)
假设第(move)次时，从(x_0+1)层丢下鸡蛋:

• 鸡蛋破了
  剩下(move-1)次机会和(i-1)个鸡蛋,可以检测([1,x_0])层楼
• 鸡蛋没破
  剩下(move-1)次机会和(i)个鸡蛋,可以检测上面的([x_0+1,x_0+1+x_1])层楼

因此，这样子可以检测(x_0+x_1+1)层
转移方程：(f[x,k]=f[x-1,k-1]+f[x-1,k]+1)

然后只要(k)循从大到小来，就可以压掉一位空间，当第一次有(f)超过(m)时，(move)就是答案了

#include <bits/stdc++.h>
int move,n,m,dp[105];
int main(){
	scanf("%d%d",&n,&m);
	for (move=0;dp[n]<m;move++)
		for (int i=n;i>=1;i--)
			dp[i]+=dp[i-1]+1;
	printf("%d",move);
}

思路有趣，代码简短，感谢王子昂同学的推荐
俗称扔鸡蛋问题：很好的一篇文章