題目描述：（直接摘抄網上的原句）
一個評估蛋的硬度方法是測量蛋從多高摔下來會碎。現在佳佳想以樓層高度作為考量依據評估蛋的硬度。如果蛋從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;
}
