【題意】：都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內。餡餅如果掉在了地上當然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側都不能站人，所以他只能在小徑上接。由于gameboy平時老呆在房間里玩游戲，雖然在游戲中是個身手敏捷的高手，但在現實中運動神經特別遲鈍，每秒種只有在移動不超過一米的范圍內接住墜落的餡餅。現在給這條小徑如圖標上坐標：

為了使問題簡化，假設在接下來的一段時間里，餡餅都掉落在0-10這11個位置。開始時gameboy站在5這個位置，因此在第一秒，他只能接到4,5,6這三個位置中其中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（假設他的背包可以容納無窮多個餡餅）

【題解】：dp，轉移超級明顯。
              狀態：dp[i][j]表示第i秒在j位置可以拿到的最大餡餅數
              轉移：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 
26 const int inf = 1 << 30;
27 #define MAX 100050
28 int dp[13][MAX], n;
29 int main() {
30     while(~scanf("%d", &n), n) {
31         int T = 0, x, t;
32         memset(dp, 0, sizeof(dp));
33         for(int i = 0; i < 13; i++) dp[i][0] = -inf;
34         dp[6][0] = 0;
35         for(int i = 0; i < n; i++) {
36             scanf("%d%d", &x, &t);
37             dp[x+1][t]++;
38             T = max(T, t);
39         }
40         for(int i = 1; i <= T; i++)
41             for(int j = 1; j <= 11; j++)
42                 dp[j][i] += max(dp[j-1][i-1], max(dp[j][i-1], dp[j+1][i-1]));
43         int ans = 0;
44         for(int i = 1; i <= 11; i++) ans = max(ans, dp[i][T]);
45         cout << ans << endl;
46     }
47     return 0;
48 }
49