50 pts

https://www.luogu.com.cn/record/194991948

#include <bits/stdc++.h>

using namespace std;

const int N = 1024, inf = 1 << 30;

int n, m, k;
int up[10050], down[10050], f[N], g[N], ans1, ans2;

struct node {
	int l = -114514, r = 1919810;
} a[10050];

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) scanf("%d%d", &up[i], &down[i]);
	for (int i = 1; i <= k; i++) {
		int x, l, r;
		scanf("%d%d%d", &x, &l, &r);
		a[x].l = l, a[x].r = r;
	}
	f[0] = inf;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= up[i] - 1; j++) g[j] = f[j];
		for (int j = up[i]; j < m; j++) 
			g[j] = min(g[j - up[i]] + 1, f[j - up[i]] + 1);
		g[m] = inf;
		for (int j = 1; j <= up[i]; j++) 
			g[m] = min(g[m], g[m - j] + 1);
		for (int j = 0; j <= up[i] - 1; j++) g[j] = inf;
		for (int j = m - down[i]; j; j--) 
			g[j] = min(g[j], f[j + down[i]]); // 应为 g[m] = min({g[m], g[m - j] + 1, f[m - j] + 1});
		for (int j = 1; j <= a[i].l; j++) 
			g[j] = inf;
		for (int j = a[i].r; j <= m; j++) 
			g[j] = inf;
		memcpy(f, g, sizeof(f));
		ans2 = inf;
		for (int j = 0; j <= m; j++) 
			ans2 = min(ans2, f[j]);//, cerr << f[j] << " ";
		//cerr << endl;
		if (ans2 >= 100000000) {
			printf("0\n%d\n", ans1);
			return 0;
		} 
		if (a[i].l > -114) ++ans1;
		memset(g, 0, sizeof(g));
	}
	printf("1\n%d\n", ans2);
	return 0;
}

75 pts

https://www.luogu.com.cn/record/194992150

#include <bits/stdc++.h>

using namespace std;

const int N = 1024, inf = 1 << 30;

int n, m, k;
int up[10050], down[10050], f[N], g[N], ans1, ans2;

struct node {
	int l = -114514, r = 1919810;
} a[10050];

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) scanf("%d%d", &up[i], &down[i]);
	for (int i = 1; i <= k; i++) {
		int x, l, r;
		scanf("%d%d%d", &x, &l, &r);
		a[x].l = l, a[x].r = r;
	}
	f[0] = inf;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= up[i] - 1; j++) g[j] = f[j];
		for (int j = up[i]; j < m; j++) 
			g[j] = min(g[j - up[i]] + 1, f[j - up[i]] + 1);
		g[m] = inf;
		for (int j = 1; j <= up[i]; j++) 
			g[m] = min({g[m], g[m - j] + 1, f[m - j] + 1}); // j 初值为 0
		for (int j = 0; j <= up[i] - 1; j++) g[j] = inf;
		for (int j = m - down[i]; j; j--) 
			g[j] = min(g[j], f[j + down[i]]);
		for (int j = 1; j <= a[i].l; j++) 
			g[j] = inf;
		for (int j = a[i].r; j <= m; j++) 
			g[j] = inf;
		memcpy(f, g, sizeof(f));
		ans2 = inf;
		for (int j = 0; j <= m; j++) 
			ans2 = min(ans2, f[j]);//, cerr << f[j] << " ";
		//cerr << endl;
		if (ans2 >= 100000000) {
			printf("0\n%d\n", ans1);
			return 0;
		} 
		if (a[i].l > -114) ++ans1;
		memset(g, 0, sizeof(g));
	}
	printf("1\n%d\n", ans2);
	return 0;
}

希望能对您有帮助！