如果你對hphp和猴子感興趣 請看《猴子》一題，但是hphp看完題後覺得出題人很笨，如果猴子的行動范圍是在n(n<=100)根水平排列的柱子的底端上，那麼還要柱子做什麼呢，干脆用木樁好了！hphp從此下定決心要改變猴子的故事，猴子依然在柱子上生活，並且以坐蟲子為快樂。每坐到一個蟲子他就快樂一點。可是他的快樂是有極限的，因為他只能在同一個柱子上垂直上下運動，或者水平的在相鄰的柱子間移動，並且移動一次時間是1s（垂直或者水平，垂直時候每一秒移動1cm和蟲子的移動速度相同诶！），如果在時間t(0<=t<=1000)猴子剛好在柱子m（1<=m<=n）上的k（0<=k<=100）位置並且此時m上的k位置恰好會出現一只蟲子，那麼猴子就可以坐到它了，也就是快樂加一點哦。現在猴子最初(0s)在1號柱子距底端s（s是最上端）cm的位置上,已知蟲子依次出台的時間和柱子號，並且蟲子是從0cm位置進入柱子的。猴子想要最快樂，你還能夠幫助它嗎~
Input
多組測試數據，每組測試數據首先給出整數n，t ，s和m(0<n<=100，0<=t<=1000，0<=s<=100)占一行。n表示總共有多少柱子，t表示游戲結束的時間，s表示每根柱子的最大高度（cm），t時間的猴子就不可以再坐蟲子咯。接下來有m行，每行有2個整數a,b,表示的是在a時間b柱子的底端會出現一只蟲子，並且以1cm/s的速度向柱子上面爬，如果爬出s點，那麼蟲子就獲救了！
Output
對於每組測試數據輸出一個整數，表示猴子快樂的最大點數。
Sample Input
3 4 3 3
0 2
1 1
2 3
3 4 4 4
0 1
1 1
0 2
1 2
1 5 4 4
0 1
1 1
2 1
3 1
1 5 3 4
0 1
1 1
2 1
3 1
Sample Output
1
0
1
2
思路引導
（1）這道題和上一道有很大的相似的，怎樣處理上下移動這個方面呢？
（2）上下移動。考慮到蟲子和猴子移動的速度是一樣的，所以說猴子根本不需要上下移動，也就是說，如果認為猴子在s位置上左、右移動就會得到一個最優值。
（3）顯然條件確定的情況下是滿足最優子結構的，即可以用dp解決。並且和“猴子”那道題有異曲同工之處。
解題報告
用mx[i][j]表示在第i時間在第j個柱子上時候能夠得到的最大的幸福值，grid[i][j]表示第i時間第j柱子是否有蟲子。那麼mx[i][j]=Max(mx[i-1][j-1],max[i-1][j],max[i-1][j+1])+grid[i][j];注意邊界情況。關鍵問題變成了grid[j][i]怎樣去求。在a時間b柱子上出現了一只蟲子，那麼它走到b的時間應該是a+s，所以如果出現a，b，那麼grid[b][a+s]=1.
源碼
#include<stdio.h>
#define MAX (1<<29)
#define N 110
#define T 10100
#define Max(a,b,c) (((a)>(b)?(a):(b))>(c)?((a)>(b)?(a):(b)):(c))
int mx[T][N],grid[N][T];
int n,limt,len,m;
int main()
{
while(scanf("%d %d %d %d",&n,&limt,&len,&m)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=0;j<limt;j++)
grid[i][j]=0;
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
grid[b][a+len]=1;
}
for(int i=1;i<=n;i++)
for(int j=0;j<limt;j++)
mx[j][i]=-MAX;
mx[0][1]=grid[1][0];
for(int i=1;i<limt;i++)
{
for(int j=1;j<=n&&j<=i+1;j++)
{
int a=-MAX,b=-MAX,c=-MAX;
if(j>1)
a=mx[i-1][j-1];
b=mx[i-1][j];
if(j<n)
c=mx[i-1][j+1];
mx[i][j]=Max(a,b,c)+grid[j][i];
}
}
int mxmx=0;
for(int i=1;i<=n;i++)
if(mx[limt-1][i]>mxmx)
mxmx=mx[limt-1][i];
printf("%d\n",mxmx);
}
return 0;
}
