题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1176
思路 因为刚开始的起点是固定的 但是终点不是固定的 所以我们可以从终点往起点推
dp[i][j] 表示 在时刻为t的时候 坐标为j 的时刻 可以获得的最多馅饼数
dp[i][j] += max(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]);
最后状态会转移到 dp[1][4], dp[1][5], dp[1][6] 去三值中的最大值
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; int dp[maxn][11]; int Move[3] = { -1, 0, 1 }; bool ok(int x) { if (x < 0 || x >= 11) return false; return true; } int main() { int n; while (scanf("%d", &n) && n) { CLR(dp, 0); int a, b; int T = -INF; for (int i = 0; i < n; i++) { scanf("%d%d", &a, &b); dp[b][a]++; T = max(T, b); } for (int i = T - 1; i >= 1; i--) { for (int j = 0; j < 11; j++) { int tmp = 0; for (int k = 0; k < 3; k++) { int x = j + Move[k]; if (ok(x)) { tmp = max(tmp, dp[i + 1][x]); } } dp[i][j] += tmp; } } int ans = max(max(dp[1][4], dp[1][5]), dp[1][6]); cout << ans << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433092.html
