题目链接：https://vjudge.net/contest/68966#problem/G
题目：
6 5 1 4 1 6 1 7 2 7 2 8 3 0Sample Output
4
思路：dp[t][x]表示在t秒x位置上所拥有的数量，过程
类似：
5 （0s）
4 5 6 (1s)
3 4 5 6 7 (2s)
2 3 4 5 6 7 8 (3s)
1 2 3 4 5 6 7 8 9 (4s)
0 1 2 3 4 5 6 7 8 9 10 (5s)
// // Created by hanyu on 2019/8/8. // #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include<math.h> #include<map> using namespace std; typedef long long ll; const int maxn=1e5+7; #define MAX 0x3f3f3f3f int main() { int n; int dp[maxn][20]; while(~scanf("%d",&n)&&n) { memset(dp,0,sizeof(dp)); int x,t; int maxt=0; for(int i=0;i<n;i++) { scanf("%d%d",&x,&t); dp[t][x]++; if(t>maxt) maxt=t;//找出最大时间 } for(int i=maxt-1;i>=0;i--) { for(int j=0;j<=10;j++) { dp[i][j]+=max(dp[i+1][j+1],max(dp[i+1][j],dp[i+1][j-1]));//三个位置上比较出最大的再加上当前的数量 } } printf("%d\n",dp[0][5]); } return 0; }
[kuangbin带你飞]专题十二 基础DP1 G - 免费馅饼 HDU - 1176
原文：https://www.cnblogs.com/Vampire6/p/11320507.html