题意：小鸟游戏，从最左边出发，到达最右边，假设，小鸟在（x，y），现在有两种走法，一种是点击K4，还有一种是保持不动，这两种情况分别可以让小鸟到（x+1，y+kX）。第二种情况是(x+1，y-Y）。地图中你有不可以到的地方，不能碰到水管和地面。现在求最小的点击次数，使得小鸟可以到达右边。（注意：不能超过最上面一行，点击以后，不会超过最上面一行）
题解：这道题刚开始看是最短路，可以用djstela去做，但是会超时。每个起点开始，发现会超时。仔细一看，发现可以用背包做。就是一个01背包套一个完全背包的问题。01背包就是往下掉，完全背包是可以往上点，两种背包套在一起。子状态dp（i，j）代表最少需要点击几次到达（i，j）这个位置，不能到达就设成正无穷大。转移方程dp（i，j）=min（dp（i-1，j+Y），dp（i，j-X）），把不能到的地方在设成正无穷。如果不能到达，就从后往前找，找到第一个可以到的列，就是最远的列far，然后记录一下哪些列有水管，输出[1, far]里的水管即可。
#include <iostream> #include <cstring> using namespace std; int n, m, k; int x[10010], y[10010]; int dp[10010][2010]; int low[10010], high[10010]; bool flag[10010]; int ans = 0x7f7f7f7f; int read() { int ret = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == ‘-‘) { f = -1; } ch = getchar(); } while (isdigit(ch)) { ret = ret * 10 + ch - ‘0‘; ch = getchar(); } return ret * f; } int main() { n = read(), m = read(), k = read(); for (int i = 1; i <= n; i++) { x[i] = read(); y[i] = read(); } for (int i = 1; i <= n; i++) { high[i] = m + 1; low[i] = 0; } for (int i = 1, p; i <= k; i++) { p = read(), low[p] = read(), high[p] = read(); flag[p] = 1; } memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i <= m; i++) { dp[0][i] = 0; } for (int i = 1; i <= n; i++) { for (int j = x[i] + 1; j <= m + x[i]; j++) { dp[i][j] = min(dp[i][j - x[i]] + 1, dp[i - 1][j - x[i]] + 1); } for (int j = m + 1; j <= x[i] + m; j++) { dp[i][m] = min(dp[i][j], dp[i][m]); } for (int j = 1; j + y[i] <= m; j++) { dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i]]); } for (int j = 1; j <= low[i]; j++) { dp[i][j] = 0x3f3f3f3f; } for (int j = high[i]; j <= m; j++) { dp[i][j] = 0x3f3f3f3f; } } for (int i = 1; i <= m; i++) { ans = min(ans, dp[n][i]); } if (ans < 0x3f3f3f3f) { cout << 1 << endl; cout << ans; } else { ans = 0; cout << 0 << endl; int far = 0; for (int i = n; i >= 0; i--) { for (int j = 1; j <= m; j++) { if (dp[i][j] < 0x3f3f3f3f) { far = i; break; } } if (far) break; } for (int i = far; i; i--) { if (flag[i]) { ans++; } } cout << ans; } return 0; }
原文：https://www.cnblogs.com/zcr-blog/p/11826973.html