题意：
一个评估蛋的硬度方法是测量蛋从多高摔下来会碎。现在佳佳想以楼层高度作为考量依据评估蛋的 硬度。如果蛋从i楼上掉下来会碎，而i-1不会，那么蛋的硬度为i。高为n层的实验楼里面有蛋卖，一个X元。佳佳开始没有蛋，并且他只能随身携带一个蛋， 不带蛋进楼需要Y元，带蛋需要Z元，做完试验之后如果还有一个蛋，可以卖掉得X/2元（卖蛋不需要进楼）。佳佳把鸡蛋扔出去后，会出楼检查蛋的情况。如果 蛋扔下后没有碎掉，佳佳一定会把蛋捡起，然后进楼，如蛋碎掉了，佳佳就不会管它。 佳佳想知道在最糟糕的情况下，测出蛋的硬度最少需要花费多少钱。
思路：
注意从最高层楼扔下来鸡蛋是一定会碎的。
设dp[i]为i层楼测鸡蛋硬度的最小花费，考虑在j层扔下一枚鸡蛋,
1.如果摔碎了，那么花费则是dp[j] + x + y; 碎了 就要进楼y+买蛋x
2.如果没摔碎，那么花费则是dp[i-j] + z; 没碎 就要带蛋进楼z
3.如果j = i - 1，则2中的花费应为 y + x - x / 2; 第一次试验了i-1层 在没碎的情况下 就有结果了 进楼y+买蛋x-卖蛋x/2
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 long long dp[1005],d1,d2; 6 long long ans; 7 8 int main(){ 9 int t; cin>>t; 10 for(int cas=1; cas<=t; cas++){ 11 int n,x,y,z; 12 cin >> n >> x >> y >> z; 13 memset(dp,0x3f,sizeof(dp)); 14 dp[0] = dp[1] = 0; 15 for(int i=2; i<=n; i++){ 16 for(int j=1; j<i; j++){ 17 d1 = dp[j]+x+y; // 碎了 就要进楼y+买蛋x 18 d2 = dp[i-j]+z; // 没碎 就要带蛋进楼z 19 if(i-j==1) 20 d2 = y+x-x/2; // 第一次试验了i-1层 在没碎的情况下 就有结果了 进楼y+买蛋x-卖蛋x/2 21 dp[i] = min(dp[i],max(d1,d2)); // 在最糟的情况的最小花费 22 } 23 } 24 cout << "Case " << cas << ": " << dp[n] << endl; 25 } 26 }