URAL/1223

哎哎，一道比较好的DP题吧~ 来贴个C++的题解。。。

膜拜朱晨光大牛~Orz。。。

#include <iostream>
#include <cmath>
using namespace std;
int EggNum,N,g[21];
inline void DP()
{
    for (int i=2;i<=N;i++)
    {
        for (int j=EggNum;j>1;j--)
        {
            g[j]+=g[j-1]+1;
            if ((j == EggNum) && (g[j] >= N))
            {
                cout << i << endl;
                return;
            }
        }
        g[1]=i;
    }
}
int main(void)
{
    while (true)
    {
        cin >> EggNum;
        if (!EggNum)  break;
        cin >> N;
        int tmp=(int)(floor(log((double)N)/log(2.0))+1.0);
        if (EggNum >= tmp)
            cout << tmp << endl;
        else
        {
            for (int i=1;i<=EggNum;i++)
                g[i]=1;
            if (g[EggNum] >= N)
                cout << '1' << endl;
            else if (EggNum == 1)
                cout << N << endl;
            else DP();
        }
    }
    return 0;
}
//by zzy

究级算法，不管是空间还是时间都是理论上最优的，可以证明复杂度为O（sqrt（n））

program cyd;
  var
    g:array[0..1,0..1000]of longint;
    i,n,m,x,k:longint;
  begin
    readln(n,m);
    while (n<>0)and(m<>0) do
      begin
        for i:=1 to n do
          g[0,i]:=1;
        x:=1; k:=0;
        while g[k,n]<m do
          begin
            inc(x); k:=1-k;
            for i:=1 to n do
              g[k,i]:=g[1-k,i-1]+g[1-k,i]+1;
          end;
        writeln(x);
        readln(n,m);
      end;
  end.

因为对空间进行了优化，所以可能不他爱好理解，具体的应为：g[i,j]:=g[i-1,j-1]+g[i-1,j]+1;

g[i,j]表示的是用j个鸡蛋试i次能达到的最大楼层，目的就是找到一个g[i-1,j]<m 且 g[i,j]>=m i就是答案。

转移方程，由目的看出，如果g[i-1,j]<m 那么对于g[i-1,j]的情况肯定能出解，那么我们必然会直接试>g[i-1,j]层，用j-1个鸡蛋试最大高度，再用最后一个鸡蛋优

化答案。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int f[15][1101]; //f[i][j]表示用i个蛋试第j层楼的最坏结果
int n,m;
int min(int a,int b)
{
	if (a<b) return a;else return b;
}
int max(int a,int b)
{
	if (a>b) return a;else return b;
}
int main()
{
	for (int i=1;i<=1000;i++)
	{
		f[1][i]=i;
		f[0][i]=0;
	}
	for (int i=1;i<=11;i++)
	{
		f[i][0]=0;
		f[i][1]=1;
	}
	for (int i=2;i<1001;i++) //枚举楼层
	{
		for (int j=2;j<11;j++) //枚举蛋数
		{
			int minn=0x3FFFFFFF;
			for (int k=1;k<=i;k++) //k表示第k层楼
			{
				minn=min(minn,max(f[j-1][k-1],f[j][i-k]));
                                //假如在第K-1层楼碎就用剩下j-1个蛋去试剩下的，如果在第k层都不碎就用就个蛋试上面的i-k层楼
			}
			f[j][i]=minn+1;
		}
	}
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		if (n==0 && m==0) break;
		if (n>10) printf("%d\n",f[10][m]);
		else printf("%d\n",f[n][m]);
	}
}
//by Exia