经典多重背包
设 \(f_{i, j}\) 表示当前在第 i 个位置，高度为 j 的最小代价，那么可以简单写出转移式：
\[f_{i, j} = \min(f_{i - 1, j + y}, f_{i - 1, j - x}) \]并且要注意一些细节：由于是多重背包，注意从低位往高位枚举，当 \(j = m\) 时，\(f_{i, j}\) 可以从 \([m - y, m)\) 转移过来。现在考虑有管道挡住的情况，显然有管道的地方永远转移不到其它地方，所以直接令这些地方为一个极大值即可。
注意到 \(f_{i, j}\) 只和 \(f_{i - 1, ?}\) 有关，所以可以用滚动数组省掉一维（然而这道题目不用省空间，\(O(nm)\) 的空间是可以过去的）
Code
#include <algorithm>
#include <iostream>
using namespace std;
using pii = pair<int, int>;
const int kV = 1e3 + 1, kN = 1e4 + 1;
int n, m, k, ans = 1e9, f[kV], g[kN];
pii a[kN];
struct AC {
int x, l, h;
bool operator<(const AC x) const {
return this->x < x.x;
}
} c[kN];
int C() {
for (int i = 1; i <= m; i++) {
if (f[i] != 1e9) {
return 0;
}
}
return 1;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
for (int i = 1; i <= k; i++) {
cin >> c[i].x >> c[i].l >> c[i].h;
}
sort(c + 1, c + k + 1);
for (int i = 1, k = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j + a[i - 1].second <= m) {
f[j] = g[j + a[i - 1].second];
} else {
f[j] = 1e9;
}
if (j - a[i - 1].first > 0) {
f[j] = min(f[j], g[j - a[i - 1].first] + 1);
g[j] = min(g[j], g[j - a[i - 1].first] + 1);
}
}
for (int j = m - a[i - 1].first; j <= m; j++) {
f[m] = min(f[m], g[j] + 1);
}
if (i == c[k].x) {
for (int j = 1; j <= c[k].l; j++) {
f[j] = 1e9;
}
for (int j = c[k].h; j <= m; j++) {
f[j] = 1e9;
}
if (C()) {
cout << "0\n" << k - 1 << '\n';
return 0;
}
k++;
}
for (int j = 1; j <= m; j++) {
g[j] = f[j];
}
}
for (int i = 1; i <= m; i++) {
ans = min(ans, f[i]);
}
cout << "1\n" << ans;
return 0;
}