[NOIP2014 提高组] 飞扬的小鸟

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXM = 1005;
const int MAXK = 10005;
int n, m, k;                 //宽、高、管道数量
int up[MAXN], down[MAXN];    //每个位置上升与下降的高度
int top[MAXN], bottom[MAXN]; //横坐标为i时的上管道底端与下管道顶端
int cnt[MAXN];               //当前位置及左边有多少个管子
int dp[MAXN][2 * MAXM];      //到每个位置的最小跳跃步数
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //输入
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> up[i] >> down[i];
        top[i] = m + 1;
        bottom[i] = 0;
    }
    top[n] = m + 1;
    bottom[n] = 0;
    for (int i = 1; i <= k; i++)
    {
        int x, b, t;
        cin >> x >> b >> t;
        cnt[x]++;
        bottom[x] = b;
        top[x] = t;
    }
    //work
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= m; i++)
        dp[0][i] = 0;
    bool flag = false;
    int R = 0;
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
    {
        cnt[i] += cnt[i - 1];
        //上升跳到(i,j)的位置
        for (int j = 1 + up[i - 1]; j <= m + up[i - 1]; j++)
            dp[i][j] = min(dp[i - 1][j - up[i - 1]] + 1, dp[i][j - up[i - 1]] + 1);
        for (int j = m + 1; j <= m + up[i - 1]; j++)
            dp[i][m] = min(dp[i][m], dp[i][j]);
        //下降到(i,j)的位置
        for (int j = 1; j <= m - down[i - 1]; j++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j + down[i - 1]]);
        //去掉不合理状态并合并
        for (int j = 1; j <= m; j++)
        {
            if (j >= top[i] || j <= bottom[i] || dp[i][j] > 0x3f3f3f3f)
                dp[i][j] = 0x3f3f3f3f;
            if (dp[i][j] != 0x3f3f3f3f)
            {
                R = max(R, cnt[i]);
                if (i == n)
                {
                    flag = true;
                    ans = min(ans, dp[i][j]);
                }
            }
        }
    }
    if (flag)
        cout << "1\n"
             << ans << "\n";
    else
        cout << "0\n"
             << R << "\n";
    return 0;
}