丢一发好理解又好写的线段树优化dp。
简要题意
给定一个长为 \(l\) 的线段，求出尽量少的不相交区间覆盖整段线段，要求题目给的所有子区间只被 \(1\) 个区间覆盖。
分析
显然题目给的子区间 \([s, e]\) 中只有 \(s\) 和 \(e\) 端点能作为线段端点，所以我们应该给 \([s + 1, e + 1]\) 打上标记，这些不能作为线段端点。
令 \(dp_i\) 为覆盖 \([0, i]\) 的最小的线段数量，要求的就是 \(\min (dp_j) + 1, j \in [i - a * 2, i - b * 2]\)。
可以很轻易的写出一段暴力程序。
dp[0] = 0;
for(int i = 2; i <= l; i += 2)
{
if(flag[i]) continue;
for(int k = a; k <= b; k ++)
{
int j = i - k * 2; // 在i, j 中间放一个线段
if(j < 0) break;
dp[i] = min(dp[i], dp[j] + 1);
}
}
发现该算法的瓶颈会在枚举 \(k\) 的复杂度太高了，考虑优化掉。
区间最小值？线段树？
每次取出区间中的最小值算出 \(dp_i\) 递推下去就行。
代码就变成了这样：
for(int i = a * 2; i <= l; i += 2)
{
if(flag[i]) continue;
int ql = max(0, i - 2 * b), qr = i - 2 * a;
dp[i] = query(ql, qr, 1) + 1;
update(i, dp[i], 1);
}
写一棵可爱的线段树就可以拉。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, l, a, b;
bool flag[N];
int dp[N];
struct segtree
{
int l, r, val;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define val(x) tr[x].val
} tr[N << 2];
void pushup(int x)
{
val(x) = min(val(x << 1), val(x << 1 | 1));
}
void build(int l, int r, int x)
{
l(x) = l, r(x) = r, val(x) = INF;
if(l == r) return;
int mid = l + r >> 1;
build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
}
void update(int pos, int v, int x)
{
if(l(x) == r(x))
{
val(x) = v;
return;
}
int mid = l(x) + r(x) >> 1;
if(mid >= pos) update(pos, v, x << 1);
else update(pos, v, x << 1 | 1);
pushup(x);
}
int query(int l, int r, int x)
{
if(l <= l(x) && r(x) <= r) return val(x);
int mid = l(x) + r(x) >> 1, res = INF;
if(l <= mid) res = query(l, r, x << 1);
if(r > mid) res = min(res ,query(l, r, x << 1 | 1));
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> l >> a >> b;
for(int i = 1; i <= n; i ++)
{
int x, y;
cin >> x >> y;
for(int j = x + 1; j <= y - 1; j ++) flag[j] = true;
}
build(0, l, 1);
update(0, 0, 1);
for(int i = a * 2; i <= l; i += 2)
{
if(flag[i]) continue;
int ql = max(0, i - 2 * b), qr = i - 2 * a;
dp[i] = query(ql, qr, 1) + 1;
update(i, dp[i], 1);
}
if(dp[l] >= INF) dp[l] = -1;
cout << dp[l] << '\n';
return 0;
}