1 /*
2 hdu1176 DP：免费馅饼
3 ymc 2008/09/22
4 题目大意：
5 人在一个[0,10]的小径上,天上会掉馅饼。
6 总共有n个馅饼，每个馅饼在t时刻掉到x位置。
7 初始位置人在x=5位置,人一秒中最多左右移动1的距离。
8 求最多能接住多少个馅饼。
9 分析与解题思路
10 用map[t][x]记录在t时刻掉在x位置的馅饼个数。
11 用ans[t][x]记录在t时刻人在x位置的时候最多能接住多少
12 个馅饼。
13 则在|x-5|<=t时
14 ans[t][x]=Max{ans[t-1][x-1],ans[t-1][x],ans[t-1][x+1]}+map[t][x];
15 注意：N＝100000时会WA，晕死。
16 */
17 #include <iostream>
18 #include <cmath>
19 using namespace std;
20 const int N=100005;
21 const int M=11;
22 int map[N][M];
23 int n;
24 int ans[N][M];
25 int step[2]={1,-1};
26 int mt;
27 void DP()
28 {
29 int Max;
30 int x1;
31 int MaxOut=0;
32 memset(ans,0,sizeof(ans));
33 // ans[0][5]=map[0][5];
34 for(int t=1;t<=mt;t++)
35 {
36 for(int x=0;x<=10;x++)
37 {
38 if(abs(x-5)>t)
39 continue;
40 Max=ans[t-1][x];
41 for(int k=0;k<2;k++)
42 {
43 x1=x+step[k];
44 if(x1<0||x1>10)
45 continue;
46 if(Max<ans[t-1][x1])
47 Max=ans[t-1][x1];
48 }
49 ans[t][x]=Max+map[t][x];
50 if(ans[t][x]>MaxOut)
51 MaxOut=ans[t][x];
52 }
53 }
54
55 printf("%d\n",MaxOut);
56 }
57 int main()
58 {
59 int x,t;
60 while(scanf("%d",&n),n)
61 {
62 memset(map,0,sizeof(map));
63 mt=0;
64 for(int i=0;i<n;i++)
65 {
66 scanf("%d %d",&x,&t);
67 map[t][x]++;
68 if(t>mt)
69 mt=t;
70 }
71 DP();
72 }
73 }