[NOIP2014]飞扬的小鸟

总体思路不多说，我就说一下为什么要先把上升的完全背包做完，再做下降的01背包 先上代码

80分代码

对每个$(i,j)(i,j)$, 把完全背包和01背包都一次性做了

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (j < low[i])
            continue;
        if (j > high[i])
            break;
        if (j - x[i] >= 1)
        {
            f[i][j] = min(f[i][j], f[i - 1][j - x[i]] + 1);
            f[i][j] = min(f[i][j], f[i][j - x[i]] + 1);
        }
        if (j == m)
            for (int kk = j - x[i]; kk <= m; kk++)
            {
                f[i][j] = min(f[i][j], f[i - 1][kk] + 1);
                if (kk < m)
                    f[i][j] = min(f[i][j], f[i][kk] + 1);
            }
        if (j + y[i] <= m)
            f[i][j] = min(f[i][j], f[i - 1][j + y[i]]);
    }
}

这样会导致一个问题，比如说，$f[i][10]f[i][10]$要用到$f[i][3]f[i][3]$来计算上升，而$f[i][3]f[i][3]$已经把上升和下降都算过了，那么就相当于多算了一种错误情况：从$i-1i-1$通过下降来到$f[i][3]f[i][3]$, 再通过$f[i][3]f[i][3]$上升。然而这是非法情况，因为从$i-1i-1$到$ii$只能上升或下降或一直保持在顶部，不可能既下降又上升。

先完全背包 再01的核心代码

for (int i = 1; i <= n; i++)
{
    for (int j = 1 + x[i]; j <= m + x[i]; j ++)
        f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1);
    for (int j = m + 1; j <= m + x[i]; j ++)
        f[i][m] = min(f[i][m], f[i][j]);
    for (int j = 1; j <= m - y[i]; j ++)
        f[i][j] = min(f[i][j], f[i - 1][j + y[i]]);
    for (int j = 1; j < low[i]; j ++)
        f[i][j] = 0x3f3f3f3f;
    for (int j = high[i] + 1; j <= m; j ++)
        f[i][j] = 0x3f3f3f3f;
}

总体AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 10010, M = 2010;
int n, m, k;
int low[N], high[N];
bool tube[N];
int f[N][M];
int x[N], y[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;

    // 将i-1号位置对i号位置的影响直接读到i号位置的数组里
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
        low[i] = 1, high[i] = m;
    }
    low[0] = 0, high[0] = m;

    for (int i = 0; i < k; i++)
    {
        int p, l, h;
        cin >> p >> l >> h;
        tube[p] = true;
        low[p] = l + 1, high[p] = h - 1;
    }

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= m; i++)
    {
        f[0][i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1 + x[i]; j <= m + x[i]; j ++)
            f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1);
        for (int j = m + 1; j <= m + x[i]; j ++)
            f[i][m] = min(f[i][m], f[i][j]);
        for (int j = 1; j <= m - y[i]; j ++)
            f[i][j] = min(f[i][j], f[i - 1][j + y[i]]);
        for (int j = 1; j < low[i]; j ++)
            f[i][j] = 0x3f3f3f3f;
        for (int j = high[i] + 1; j <= m; j ++)
            f[i][j] = 0x3f3f3f3f;
    }

    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= m; i++)
    {
        ans = min(f[n][i], ans);
    }
    if (ans == 0x3f3f3f3f)
    {
        int res = 0;
        int i; // 最后能通过的坐标
        for (i = n; i >= 1; i--)
        {
            int j;
            for (j = 1; j <= m; j++)
            {
                if (f[i][j] < 0x3f3f3f3f)
                {
                    break;
                }
            }
            if (j <= m)
                break;
        }
        for (int j = 1; j <= i; j++)
        {
            if (tube[j])
                res++;
        }
        cout << 0 << '\n'
             << res << '\n';
    }
    else
    {
        cout << 1 << '\n'
             << ans << '\n';
    }
    return 0;
}