http://acm.hdu.edu.cn/showproblem.php?pid=1176

简单dp

#include<stdio.h>
#include<string.h>
int fallx[100010][11];
int a[100001][11];
int main(){
 int i,n,x,t,max,total,sum,q,j;
 while (scanf("%d",&n)!=EOF&&n){
  memset(fallx,0,sizeof(fallx));
  memset(a,0,sizeof(a));
  for(max=0,i=0;i<n;i++){
   scanf("%d%d",&x,&t);
   fallx[t][x]++;
   if (t>max)
                max=t;
  }
  total=0;
  for(i=4;i<=6;i++){
   a[1][i]=fallx[1][i];
   if (a[1][i]>total)
    total=a[1][i];
  }
  for(i=2;i<=max;i++)
  {
   for(j=0;j<=10;j++)
   {
    if(j==0)
     sum=a[i-1][j] > a[i-1][j+1] ? a[i-1][j] : a[i-1][j+1];
    else if(j==10)
     sum=a[i-1][j-1] > a[i-1][j] ? a[i-1][j-1] : a[i-1][j];       
    else
    {
     q=a[i-1][j] > a[i-1][j+1] ? a[i-1][j] : a[i-1][j+1];
     sum=a[i-1][j-1] > q ? a[i-1][j-1] : q;
    }
    a[i][j]=sum+fallx[i][j];
    if(a[i][j]>total)
     total=a[i][j];
   }
  }
  printf("%d\n",total);
 }
 return 0;
}