【题意】：都说天上不会掉馅饼，但有一天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