题意 ： 中文题。在直线上接馅饼，能接的最多是多少。
思路 ：这个题其实以前做过。。。。。你将这个接馅饼看成一个矩阵，也不能说是一个矩阵，反正就是一个行列俱全的形状，然后秒当行，坐标当列，这也就是转化成了数字三角形问题，从下往上找最大路径。下边这个图正好是某位大神的，让我不厚道的截过来了。。。。注意一下边界。
第0秒 5 （这里的数字指的是第N秒可能到达的位置坐标）
第1秒 4 5 6
第2秒 3 4 5 6 7
第3秒 2 3 4 5 6 7 8
第4秒 1 2 3 4 5 6 7 8 9
第5秒 0 1 2 3 4 5 6 7 8 9 10
第6秒 0 1 2 3 4 5 6 7 8 9 10
第7秒 .................
可以发现从第5秒开始之后就都是 0 1 2 3 4 5 6 7 8 9 10 ，所以第5秒之前的情况单独写一下，然后第5秒之后，注意一下边界 0和10这两个位置，特判一下，其他的和第四秒之前的代码一样，就好了。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std ; int dp[150000][100] ; int main() { int n ; while(~scanf("%d",&n)) { if(n == 0) break ; int x, y ,b = 0; memset(dp,0,sizeof(dp)) ; for(int i = 0 ; i < n ; i++) { scanf("%d %d",&x,&y) ; dp[y][x]++ ; b = max(b,y) ; } for(int i = b-1 ; i >= 0 ; i--) { for(int j = 1 ; j <= 9 ; j++) dp[i][j] += max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1])) ; dp[i][0] += max(dp[i+1][0],dp[i+1][1]) ; dp[i][10] += max(dp[i+1][9],dp[i+1][10]) ; } printf("%d\n",dp[0][5]) ; } return 0 ; }
HDU 1176 免费馅饼（DP）,布布扣,bubuko.com
原文：http://www.cnblogs.com/luyingfeng/p/3574356.html
