题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1176
思路：
这道题不复杂，很明显是个dp题，数据比较大，搜索应该会超时，想到如何初始化，注意细节就差不多了。定义dp数组，边输入边初始化，dp[i][j]表示第i秒j处的掉落馅饼个数。dp过程从最后一秒逆向进行更方便，过程中dp[i][j]表示逆向到第i秒j处得到馅饼的最大值。有个坑点：最后输入的一组数据的时间不一定是最后一秒，我在这wa了一发。详见代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,x,t,tt,dp[100005][15]; 5 6 int main(){ 7 while(scanf("%d",&n)!=EOF&&n){ 8 memset(dp,0,sizeof(dp)); 9 tt=0; 10 while(n--){ 11 scanf("%d%d",&x,&t); 12 if(t>tt) tt=t; 13 dp[t][x]++; 14 } 15 for(int i=tt-1;i>=0;i--) 16 for(int j=0;j<=10;j++){ 17 if(j==0) dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]); 18 else if(j==10) dp[i][j]+=max(dp[i+1][j-1],dp[i+1][j]); 19 else dp[i][j]+=max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1])); 20 } 21 printf("%d\n",dp[0][5]); 22 } 23 return 0; 24 }
原文：https://www.cnblogs.com/FrankChen831X/p/10393303.html