LOJ #2500. 「NOIP2014」飞扬的小鸟

题目链接：​​传送门​​

不知不觉这么久没更了
上了一阵子文化课，还比较颓没怎么做题
就做了做noip历年的题
也没什么好发的
挑了一个，写了些注释

#include <bits/stdc++.h>
#define

using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, k, d[A], u[A], pass, ans = inf;
int x[A], y[A], f[A][1010], tmp; bool cub[A];

int main(int argc, char const *argv[]) {
  cin >> n >> m >> k; tmp = k;
  for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]), d[i] = 1, u[i] = m;
  d[n] = 1; u[n] = m; //预先给每个位置设上边界
  for (int i = 1, p, l, h; i <= k; i++) {
    scanf("%d%d%d", &p, &l, &h); cub[p] = 1;
    d[p] = l + 1; u[p] = h - 1; //不能碰到边所以+1 -1
  }
  memset(f, 0x3f, sizeof f);
  for (int i = 1; i <= m; i++) f[0][i] = 0; //初始时在哪个位置都可以
  for (int i = 1; i <= n; i++) {
    for (int j = x[i - 1]; j <= m; j++) {
      f[i][j] = min(f[i][j], f[i][j - x[i - 1]] + 1), //去掉第一维i之后就是完全背包的转移
      f[i][j] = min(f[i][j], f[i - 1][j - x[i - 1]] + 1);
      if (j == m) for (int k = m - x[i - 1]; k <= m; k++) //到顶的特判
        f[i][j] = min(f[i][j], f[i][k] + 1), f[i][j] = min(f[i][j], f[i - 1][k] + 1);
    }
    for (int j = d[i]; j <= u[i]; j++) //从上一个位置掉下来
      if (j + y[i - 1] <= m) f[i][j] = min(f[i][j], f[i - 1][j + y[i - 1]]);
    for (int j = 1; j <= d[i] - 1; j++) f[i][j] = inf; //不能通过的水管
    for (int j = u[i] + 1; j <= m; j++) f[i][j] = inf;
  }
  for (int i = n; i >= 1; i--) { //从后往前判断是否可到达这个水管
    for (int j = d[i]; j <= u[i]; j++) if (f[i][j] < inf) ans = min(ans, f[i][j]);
    if (ans != inf) break; //有能到的即可通过输出1
    if (cub[i]) tmp--; //否则看最多通过多少水管
  }
  if (tmp == k) cout << 1 << endl << ans << endl;
  else cout << 0 << endl << tmp << endl;
  return 0;
}