如果你对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 Output 对于每组测试数据输出一个整数，表示猴子快乐的最大点数。 Sample Input 3 4 3 3 Sample Output 1 思路引导 （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
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
0
1
2
#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
for(int i=0;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
mx[0][1]=grid[1][0];
for(int i=1;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
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;
}