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