解题报告 P1941 飞扬的小鸟

虽说 AFO 了，但是我做下题总还是可以的吧我不想学文化课

题目内容

flappy bird 的改编题，地图为 n\times m，分别是长和高。每秒钟内可以点击多次屏幕，在第 i 位置处点击一次屏幕可以在下一秒上升 x_i 格，不点击屏幕下降 y_i 格，不能碰到管道或者触底（高度为 0），求如果可以通过游戏的最小点击屏幕次数或不可以通过游戏的话最多通过的管道数。

解题思路

考虑 f_{i,j} 表示到达 (i,j) 的最少点击次数，如不能到达用 INF 表示。

于是可以将状态的转移抽象成背包，每次可以选择点击无数次或者下降一次，转移方程如下：

f_{i,j}=\min(f_{i,j-x_i},f_{i-1,j-x_i})+1

这是上升来的，意义就是从前一秒的状态点击一次或者从当前秒再点击一次取最优

f_{i,j}=\min(f_{i,j},f_{i-1,j+y_i})

这就是下降来的

这题需要注意的地方：

• 上升的过程是一个完全背包（可以点击屏幕无限次），下降的是 0-1 背包
• 有可能会飞出去（大于 m），这个时候要特判，将其还原

我使用了结构体封装地图的每一格，包含了是否有管道，下降/上升的高度以及最高能通过的高度以及最低能通过的高度。

最后统计答案的时候如果不能过，那就从最后往前寻找第一个能过的点，然后统计前面有多少管道

代码：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define a(x) game[x]
using namespace std;

const int maxn = 10005, INF = 0x3f3f3f3f;
int n, m, k;
int f[maxn][3005];

struct node
{
    int x, y, high, low;
    bool flag;
} game[maxn];

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++)
    {
        a(i).x = read(), a(i).y = read();
        a(i).high = m, a(i).low = 1;
    }
    int p, l, h;
    for (int i = 1; i <= k; i++)
    {
        p = read(), l = read(), h = read();
        a(p).flag = 1,
        a(p).high = h - 1,
        a(p).low = l + 1;
    }
    memset(f, INF, sizeof(f));
    for (int i = 1; i <= m; i++)
        f[0][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = a(i).x + 1; j <= m + a(i).x; j++)
            f[i][j] = min(f[i][j], min(f[i][j - a(i).x] + 1, f[i - 1][j - a(i).x] + 1));
        for (int j = m; j <= m + a(i).x; j++)
            f[i][m] = min(f[i][m], f[i][j]);
        for (int j = 1; j <= m - a(i).y; j++)
            f[i][j] = min(f[i][j], f[i - 1][j + a(i).y]);
        for (int j = 1; j < a(i).low; j++)
            f[i][j] = INF;
        for (int j = m; j > a(i).high; j--)
            f[i][j] = INF;
    }
    int ans = INF;
    for (int i = 1; i <= m; i++)
        ans = min(ans, f[n][i]);
    if (ans < INF)
    {
        printf("1\n%d\n", ans);
        return 0;
    }
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (f[i][j] < INF)
            {
                ans = 0;
                for (int t = 1; t <= i; t++)
                    if (a(t).flag)
                        ans++;
                printf("0\n%d\n", ans);
                return 0;
            }
}