#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*問題:We are playing the Guess Game. The game is as follows:I pick a number from 1 to n. You have to guess which number I picked.Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.Example:n = 10, I pick 8.First round:  You guess 5, I tell you that it's higher. You pay $5.Second round: You guess 7, I tell you that it's higher. You pay $7.Third round:  You guess 9, I tell you that it's lower. You pay $9.Game over. 8 is the number I picked.You end up paying $5 + $7 + $9 = $21.分析：明顯得，如果把答案設置在為n，采用二分法需要獲取的代價是最多的。假設n=10,最終選取的也是10，剛開始low = 1 , high=10 , mid=(1+10)/2=5,付出5  , (low + high)/2low = 6 , high=10 , mid=8,    ( (low+high)/2 + 1 + high ) / 2 = 3/4 * high + 1/4 * low + 1/2 low = 9 , high=10, mid=9 ，low = 10, high=10 , mid=10,猜中總共花費=5 + 8 + 9 = 22n=9,5+7+8=20輸入:109輸出:1614用動態規劃來做：關鍵:1 參考：http://blog.csdn.net/adfsss/article/details/51951658設任意猜一個數為i,保證獲勝說花的錢：i + max( dp(1,i-1) , dp(i+1,n) )這里dp(x,y)表示猜范圍在(x,y)的數保證能贏應花的錢遍歷1~n作為猜的數，求出其中的最小值就是答案。2//遞歸計算，因為要保證贏，我們一直假設當前猜數i是猜錯的，然后一直到最后start >= end，就可以說明猜正確，最后一次耗費0int temp = i + max( cost(dp , start , i - 1 ) , cost(dp , i+1 , end) );//對于每個初始猜數i，計算其最多需要多少錢才能猜正確，然后從里面選擇一個初始猜數最小的即可result = min(temp , result);dp.at(start).at(end) = result;//記錄最終結果，便于記憶化搜索*/class Solution {public:	int cost(vector< vector<int> >& dp , int start , int end)	{		if(dp.empty() ||start < 0 || end >= dp.size() || start >= end)		{			return 0;		}		if(dp.at(start).at(end) != 0)		{			return dp.at(start).at(end);		}		int result = INT_MAX;		for(int i = start ; i <= end ; i++)		{			//遞歸計算，因為要保證贏，我們一直假設當前猜數i是猜錯的，然后一直到最后start >= end，就可以說明猜正確，最后一次耗費0			int temp = i + max( cost(dp , start , i - 1 ) , cost(dp , i+1 , end) );			//對于每個初始猜數i，計算其最多需要多少錢才能猜正確，然后從里面選擇一個初始猜數最小的即可			result = min(temp , result);		}		dp.at(start).at(end) = result;//記錄最終結果，便于記憶化搜索		return result;	}    int getMoneyAmount(int n) {		vector< vector<int> > dp(n + 1 , vector<int>(n+1 , 0));		int result = cost(dp , 1 , n);		return result;	}};void PRocess(){	 int num;	 Solution solution;	 while(cin >> num )	 {		 int result = solution.getMoneyAmount(num);		 cout << result << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}