题目大意：
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）


解题思路：1）由题目可以知道，在某个时间点在某点接住馅饼，则前一个时间点必须在这个点的左边，右边或者就在这个点。
              2）根据题设，我们不妨设dp[i][j]为在第i秒在j处接住的馅饼。
                      则有：    dp[i][j]=Max{dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]}+a[i][j];


代码
 1#include <iostream>
 2#include <cstdio>
 3#include <cmath>
 4#include <algorithm>
 5#include <cstring>
 6
 7using namespace std;
 8
 9int a[100010][15];
10int dp[100010][15];
11int t,n,p,q,maxx;
12
13int main()
14{
15    while (~scanf("%d",&n))
16    {
17        if (n==0) break;
18        t=-(1<<30);
19        memset(a,0,sizeof(a));
20        memset(dp,0,sizeof(dp));
21        for (int i=1; i<=n; i++)
22          {
23              cin >> p >> q;
24              a[q][p]++;
25              if (t<q) t=q;
26          }
27        dp[1][5]=a[1][5];
28        dp[1][6]=a[1][6];
29        dp[1][4]=a[1][4];
30        for (int i=1; i<=t-1; i++)
31        {
32             for (int j=0; j<=10; j++)
33             {
34                 if (dp[i+1][j+1]<a[i+1][j+1]+dp[i][j] && j<10)
35                    dp[i+1][j+1]=dp[i][j]+a[i+1][j+1];
36                 if (dp[i+1][j]<a[i+1][j]+dp[i][j])
37                    dp[i+1][j]=dp[i][j]+a[i+1][j];
38                 if (dp[i+1][j-1]<a[i+1][j-1]+dp[i][j] && j>0)
39                    dp[i+1][j-1]=dp[i][j]+a[i+1][j-1];
40             }
41        }
42        maxx=-(1<<30);
43        for (int i=1; i<=11; i++)
44           if (dp[t][i]>maxx) maxx=dp[t][i];
45        cout << maxx << endl;
46    }
47    return 0;
48}
49
：