地址：http://acm.hdu.edu.cn/showproblem.php?pid=1176
中文题意不多解释了。
建一个二维dp数组，dp[ i ][ j ]表示第 i 秒落在 j 处一个馅饼。我们需要倒着DP，为什么呢，从 0秒，x=5处出发，假如沿数组正着往下走，终点到哪里我们是不知道的，沿这个路线能最大值，下一秒就未必是最大值。但是我们知道起点，所以我们从终点开始走，走到dp[ 0 ][ 5 ]为止。由于这个总路线存在着诸多未知情况，但是有一点我们可以确定：
i , j
i+1,j-1 i+1,j i+1，j+1
对于dp[ i ][ j ]这个点，想走到下一步，肯定要加上下一步的更大的值，这个东西是不会变的。所以从最后时间点max-1（其实从max也是可以过的）开始往上走，每次取 i ,j 的下一行三个数的最大值，再加上i,j就可以了。得到方程：
dp【i】【j】+= max（dp【i+1】【j-1】，dp【i+1】【j】，dp【i+1】【j+1】）；
最后输出dp[0][5]这个起点就可以了。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int maxn=1e5+10; int dp[maxn][12]; int main() { int n; while(scanf("%d",&n)) { if(n==0) break; memset(dp,0,sizeof(dp)); int t,x; int maxx=-1; for(int i=1 ;i <= n;i++) { scanf("%d%d",&x,&t); dp[t][x]++; if(t>maxx) maxx=t; } for(int i=maxx-1;i>=0;i--) { for(int j=0;j<=10;j++) { int mid = max(dp[i+1][j-1],dp[i+1][j]); dp[i][j]+=max(mid,dp[i+1][j+1]); } } printf("%d\n", dp[0][5]); } }
原文：https://www.cnblogs.com/liyexin/p/12683102.html