一、題目大意
都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。這餡餅別處都不掉，就掉落在他身旁的10米范圍內。餡餅如果掉在了地上當然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側都不能站人，所以他只能在小徑上接。由于gameboy平時老呆在房間里玩游戲，雖然在游戲中是個身手敏捷的高手，但在現實中運動神經特別遲鈍，每秒種只有在移動不超過一米的范圍內接住墜落的餡餅。為了使問題簡化，假設在接下來的一段時間里，餡餅都掉落在0-10這11個位置。開始時gameboy站在5這個位置，因此在第一秒，他只能接到4,5,6這三個位置中期中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（假設他的背包可以容納無窮多個餡餅）請自行設定輸入輸出和測試數據。
二、題目簡化
餡餅都掉落在0-10這11個位置。開始時gameboy站在5這個位置，每秒移動距離為1，因此在第一秒，他只能接到4,5,6這三個位置中期中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（假設他的背包可以容納無窮多個餡餅）請自行設定輸入輸出和測試數據。
三、解題思想
因為在何時何地掉下餡餅都是自己輸入的，所以可以把這些數據存入一個X代表時間、Y代表空間的二維數組里，對這個數組進行DP。關鍵在于從末尾往（0，5）DP，最后跳出循環。還有一個值得注意的問題就是不要讓數組溢出。下列代碼在DP時從三個方向DP，數組邊緣處（左邊緣、右邊緣）是兩個方向DP。
四、具體實現
#include<stdlib.h>
#include<iostream>
using namespace std;
int bing[1000][12];//記錄烙餅掉下的時間和位置，行數為時間，列數為位置
int max1(int a, int b, int c)//比較三數大小
{int max = 0;max = a>b ? a : b;//a,b之間較大值傳給maxmax = max>c ? max : c;//max，c之間最大者傳給maxreturn max;
}
int max2(int a, int b)//用于兩數比較，判斷臨界值時使用
{int max = 0;max = a > b ? a : b;return max;
}
int result(int bing[][12],int tm)//從三個方向，回溯找出最大值
//（邊界值時只有兩個，下、左或下、右）所以用max1，max2來比較
{for (int i = tm - 1; i >= 0; i--)//用i代表時間{for (int j = 0; j <=10; j++)//用j代表位置{if (j == 0)bing[i][j] += max2(bing[i + 1][j], bing[i + 1][j + 1]);else if (j == 10)bing[i][j] += max2(bing[i + 1][j], bing[i + 1][j - 1]);elsebing[i][j] += max1(bing[i + 1][j], bing[i+1][j-1], bing[i + 1][j + 1]);//回溯時將原有的時刻-位置記錄，改為烙餅最大值}}return bing[0][5];
}
int main()
{int n = 0;//烙餅的總數cout << "請輸入烙餅的總數：";cin>>n;//用作循環變量cout << "請按照下列格式輸入何時何地會掉烙餅:"<<endl<<"例如1 2代表：在第一秒，會有一個餅子掉落在2的位置" << endl;int i = 0;//用于循環的變量int tm = 0;//確定一個最大的時間刻度。for (i = 0; i <n; i++)//記錄掉餅的時間和位置{int x, y;//x代表時間，y代表位置cin >> x >> y;bing[x][y]++;if (y > tm)tm = y;//記錄一個時刻最大值}int sum = 0;//最后餅的總數sum=result(bing,tm);//調用計算函數cout<<"gameboy最多能獲得的烙餅數為：" <<sum<<endl;system("pause");return 0;
}
五、圖片展示
DP過程開始時是這樣的：藍色代表與它接觸的橘黃色塊與他本身的加和，三者或兩者（邊緣）相加后的結果。就是代碼中“bing[i][j] += max2(bing[i + 1][j], bing[i + 1][j + 1])"中的bing[i][j];（結合著代碼看更清楚一點）
然后逐步搜索：
第一次內循環完的情況：
第二次內循環完的情況，此時（2，7）的餅數已由原來的2變為3：
第三次內循環完的情況：
第四次內循環完：
實驗結果：
