UVA 4996 Scientific Experiment
题目描述：（直接摘抄网上的原句）
一个评估蛋的硬度方法是测量蛋从多高摔下来会碎。现在佳佳想以楼层高度作为考量依据评估蛋的硬度。如果蛋从i楼上掉下来会碎，而i-1不会，那么蛋的硬度为i。高为n层的实验楼里面有蛋卖，一个X元。佳佳开始没有蛋，并且他只能随身携带一个蛋，不带蛋进楼需要Y元，带蛋需要Z元，做完试验之后如果还有一个蛋，可以卖掉得X/2元（卖蛋不需要进楼）。佳佳把鸡蛋扔出去后，会出楼检查蛋的情况。如果蛋扔下后没有碎掉，佳佳一定会把蛋捡起，然后进楼，如蛋碎掉了，佳佳就不会管它。 佳佳想知道在最糟糕的情况下，测出蛋的硬度最少需要花费多少钱。
——————————————————————————————————————————————————
题目思路：
此题一开始分析样例时，以为只会有三种策略：二分，从上向下，从下向上。
后来到7 2 2时不再成立了。因为以上三种策略只适用于极限情况。若xyz接近，则问题就不是那么简单了。
再仔细分析问题，可以发现可以把问题划分掉，用很优美的dp解决掉。
分析可发现， 从1..n-1和 2..n 层分别检测蛋的硬度，其最坏的结果值应该是一样的（假设两者最初都是不带蛋进入楼房）。也就是说，问题与具体是哪个楼层无关，而只与楼层总数有关系。
故设 dp[i] 为 待测楼层总数为 i （此时我们默认i层是最高层，蛋会碎），一开始不携带鸡蛋，且站在楼外面时，在最糟糕情况下检测出蛋硬度的最少花费。
当我们还有i层待测时，假设我们从j (j<i)层扔下来 ，若蛋碎了，那么还剩下 j层要检测（第j层变成最高楼层，默认是蛋会碎，符合dp[i]的定义），则从 dp[i] 转移来； 若蛋没碎，那么还剩下 i-j层要检测（第j层变成了第0层，默认是不碎的们依然符合dp[i]定义），但是由于此时蛋没碎， 还要把蛋带着进去，而dp[i]的定义是不带鸡蛋进去，那么就要从
dp[i-j] - (x+y)+z 转移来，即减掉不带蛋进楼且进楼买蛋的费用，加上带蛋进楼的费用。
即 dp[i] = max(dp[j], dp[i-j] - (x+y)+z) (j<i) 。
另外，边界值。dp[1] 显然为0 。且 当 i-j 为1的时候，即到了n-1层 蛋还没碎的时候，显然我们知道硬度就是n-1，不需要检测了，那个没坏的蛋就可以卖掉了 ，此时变为 dp[i] = max(dp[j], -x/2) (j == i-1)。
这题的关键问题是要想明白，结果与你在哪个楼层无关，而是与待检测的楼层的数目有关。并搞清边界值。
——————————————————————————————————————————————————
源代码：
[cpp]
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <map>
using namespace std;
#define maxn 1010
#define INF 1000000000
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)>(b)?(b):(a))
int dp[maxn];
int x = 0,y = 0,z = 0;
void solve(int n)
{
int i = 0,j = 0;
int ans = 0;
dp[1] = 0;
for(i = 2;i<=n;i++)
{
ans = INF;
for(j = 1;j<i;j++)
{
int t1 = dp[j];
int t2 = dp[i-j]-x-y+z;
if(i-j == 1)
t2 = -x/2;
ans = min(ans,max(t1,t2));
}
dp[i] = ans + x + y;
}
}
int main()
{
int n = 0,k = 0,t = 0;
scanf("%d",&t);
for(k = 1;k<=t;k++)
{
scanf("%d%d%d%d",&n,&x,&y,&z);
solve(n);
printf("Case %d: %d\n",k,dp[n]);
}
return 0;
}
补充：软件开发 , C++ ,
