原题见这里
关于解题的详细步骤都已经在代码注释里面了，这里一定要注意，刚开始gameboy在位置5,因此在第5秒钟之前，他的活动范围有限，所以，在循环的时候j的范围不一定能从0到10
#include <iostream>using namespace std;int a[100001][11];int dp[2][11];int main() { //dp[i][j]表示第i秒钟在位置j获得的最多的饼 //a[i][j]表示第i秒钟在位置j落下的饼的数量 //那么求解dp[i][j]的时候,分三种情况 //1.第i-1秒在j-1 或0 dp[i][j] = dp[i-1][j-1] + a[i][j] //2.第i-1秒在j dp[i][j] = dp[i-1][j] + a[i][j] //3.第i-1秒在j+1 或10 dp[i][j] = dp[i-1][j+1] + a[i][j] //那么状态转移方程为 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + a[i][j]; //优化 每一次只用到了i-1的信息，因此可以优化哦 // dp[t][j] = max(dp[1-t][j-1], dp[1-t][j], dp[1-t][j+1]) + a[i][j]; int N, m, x, T, begin, end; while (scanf("%d", &N) != EOF && N) { memset(a, 0, sizeof(a)); memset(dp, 0, sizeof(dp)); m = 0; while (N--) { scanf("%d%d", &x, &T); ++a[T][x]; m = max(m, T); } int t = 1; for (int i = 1; i <= m; ++i) { begin = max(5-i, 0); end = min(5+i, 10); // 如果i = 1 的话，也就是说第1秒钟,j的位置只能是[4, 6]; // 如果i = 2 的话, 也就是说第2秒钟,j的位置只能是[3, 7]; // 如果i = 3 的话, 也就是说第3秒钟,j的位置只能是[2, 8]; // 如果i = 4 的话, 也就是说第4秒钟,j的位置只能是[1, 9]; // 如果i >= 5 的话, 也就是说第5秒钟及以后,j的位置可以是[0, 10]; //没有到达的i, j默认都为0，比如dp[1][3]也就是第1秒钟在位置3获得的馅饼，显然，第一秒钟 //不可能从5跑到3,所以dp[1][3] = 0 for (int j = begin; j <= end; ++j) { dp[t][j] = max(max(dp[1-t][max(0, j-1)], dp[1-t][j]), dp[1-t][min(10, j+1)] ) + a[i][j]; } t = 1 - t; } int MAX = -1; for (int j = 0; j <= 10; ++j) MAX = max(MAX, dp[m%2][j]); cout << MAX << endl; } return 0;}注:鄙人最近按照此分类来刷题，假期的最低限度是刷掉所有的DP类，并且每一道题目写一个解题报告，如果有志同道合的朋友，欢迎加QQ 823797837共同学习交流，也可以加群ACM新手群161986576，老鸟飞过