算法
(完全背包) $O(nm)$
一个简单的思路,用 f[i][j]
表示到第 $i$ 列高度为 $j$ 需要的最小点击次数。
枚举在第 $i - 1$ 列点 $k$ 次屏幕,用 $f[i - 1][j - k * up[i - 1]] + k$ 来更新 $f[i][j]$。
也就是当成多重背包来做,这样的时间复杂度是 $nm^2$,只能得到 $70$ 分。
需要使用单调队列优化,才能做到 $O(nm)$。
更简单的做法:
点屏幕当成完全背包来做:
$$ f[i][j] = \min(f[i][j], f[i - 1][j - up[i - 1]] + 1) $$
$$ f[i][j] = \min(f[i][j], f[i][j - up[i - 1]] + 1) $$
假设第 $i$ 列没有管子,更新完成所有的 $f[i][j]$ 之后,把管子对应的部分的 $f[i][j]$ 设置为 $\rm INF$。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
bool chmin(int& a, int b) { if (a > b) { a = b; return 1; } return 0; }
const int N = 10010;
const int M = 1010;
int up[N], down[N], l[N], r[N];
int f[N][M];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; ++i) cin >> up[i] >> down[i];
for (int i = 1; i <= n; ++i) l[i] = 0, r[i] = m + 1;
for (int i = 1; i <= k; ++i) {
int x;
cin >> x;
cin >> l[x] >> r[x];
}
const int INF = 1001001001;
f[0][0] = INF;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j)
f[i][j] = INF;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j >= up[i - 1]) {
// 点一下
chmin(f[i][j], f[i - 1][j - up[i - 1]] + 1);
// 点多下
chmin(f[i][j], f[i][j - up[i - 1]] + 1);
}
if (j == m) { // 天花板的转移
for (int k = j - up[i - 1]; k <= m; ++k) {
chmin(f[i][j], f[i - 1][k] + 1);
chmin(f[i][j], f[i][k] + 1);
}
}
}
for (int j = 1; j <= m; ++j) {
if (j + down[i - 1] <= m)
chmin(f[i][j], f[i - 1][j + down[i - 1]]);
}
for (int j = 0; j <= l[i]; ++j) f[i][j] = INF;
for (int j = r[i]; j <= m; ++j) f[i][j] = INF;
}
int ans1 = INF;
for (int i = 1; i <= m; ++i) chmin(ans1, f[n][i]);
if (ans1 < INF) {
cout << "1\n" << ans1;
return 0;
}
int last = 1;
for (int i = 1; i <= n; ++i) {
int ok = 0;
for (int j = 1; j <= m; ++j) if (f[i][j] < INF) ok = 1;
if (!ok) {
last = i;
break;
}
}
int ans2 = 0;
for (int i = 1; i < last; ++i) {
if (l[i] > 0 or r[i] <= m)
++ans2;
}
cout << "0\n" << ans2;
return 0;
}
Orz