题目链接： 传送门
#include <iostream> #include <cstring> #include <algorithm> using namespace std; //一定要注意dp开的大小，这是个坑 int m, t, x, dp[200010][12]; int main() { while(scanf("%d", &m) != EOF) { if(m == 0) break; int time = 0; memset(dp, 0, sizeof(dp)); for(int i = 0; i < m; i++) { //更新每个点的馅饼数 scanf("%d%d", &x, &t); dp[t][x]++; //记录下最大的时间点 if(time < t) time = t; } //从下往上更新 for (int i = time - 1; i >= 0; i--) { //更新每一个点 for (int j = 0; j <= 10; j++) { //特判这个点在最左边的情况 if(j == 0) dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]); //特判这个点在最右边的情况 else if(j == 10) dp[i][j] += max(dp[i + 1][j], dp[i + 1][j - 1]); //正常的情况 else dp[i][j] += max(dp[i + 1][j], max(dp[i + 1][j + 1], dp[i + 1][j - 1])); } } //输出起点的最优解 printf("%d\n", dp[0][5]); } }这道题可用动态规划来做,这道题与三角形最小路径和相似。 首先分析一下这个问题的子问题，这道题涉及到两个变量，第一个是时间，第二个是点。所以我们可以用i来表示前i个馅饼的最佳解，然后用j表示点的位置。 接下来讲讲状态转移方程：max(dp[i + 1][j], max(dp[i + 1][j + 1], dp[i + 1][j - 1])) 每次在上一个情况下（即i + 1），寻找其相邻点的最大值（两个靠边的点需要特判），然后更新当前位置的最优解。然后从最后的情况往前更新，最后输出dp[0][5]（即起点的最优解）即可。 说说数据处理，每次输入时间和馅饼所在点，然后相应点的馅饼数自加，每次更新时，当前点加上上一个状态的最优解。
