P1941 [NOIP2014 提高组] 飞扬的小鸟-526互联

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10005;
const int M = 1005;
const int INF = 1e9;
int up[N], down[N], low[N], high[N], dp[2][M];
bool pipe[N];
int main() {
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &up[i], &down[i]);
		low[i] = 0;
		high[i] = m + 1;
	}
	for (int i = 1; i <= k; i++) {
		int h, l, p;
		scanf("%d%d%d", &h, &l, &p);
		low[h] = l; high[h] = p; pipe[h] = true;
	}
	int cnt = 0;
	bool ok = true;
	for (int i = 1; i <= n; i++) {
		// init
		int cur = i % 2, pre = 1 - cur;
		for (int j = 0; j <= m; j++) dp[cur][j] = INF;
        // up: +up
		for (int j = 0; j <= m; j++) { // 管道位置要先当成可达状态
			int from = j - up[i];
			if (from > 0 && dp[pre][from] != INF) dp[cur][j] = min(dp[cur][j], dp[pre][from] + 1);
			if (from > 0 && dp[cur][from] != INF) dp[cur][j] = min(dp[cur][j], dp[cur][from] + 1);
        }
		// top
		if (high[i] == m + 1) {
			for (int j = m - up[i]; j <= m; j++) {
                if (dp[pre][j] != INF) dp[cur][m] = min(dp[cur][m], dp[pre][j] + 1);
                if (dp[cur][j] != INF) dp[cur][m] = min(dp[cur][m], dp[cur][j] + 1);
            }
		}
		// down: -down
        // 下降的0/1背包在上升的完全背包之后计算
		for (int j = high[i] - 1; j >= low[i] + 1; j--) {
			int from = j + down[i];
			if (from <= m && dp[pre][from] != INF) dp[cur][j] = min(dp[cur][j], dp[pre][from]);
        }
		// check
		bool flag = false;
		for (int j = low[i] + 1; j <= high[i] - 1; j++) {
			if (dp[cur][j] != INF) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			ok = false;
			printf("0\n%d\n", cnt);
			break;
		}
		if (pipe[i]) cnt++;
        for (int j = 0; j <= low[i]; j++) dp[cur][j] = INF;
        for (int j = high[i]; j <= m; j++) dp[cur][j] = INF;
	}
	if (ok) {
		printf("1\n");
		int ans = INF;
		for (int i = low[n] + 1; i <= high[n] - 1; i++) ans = min(ans, dp[n % 2][i]);
		printf("%d\n", ans);
	}
	return 0;
}