题目
实际上经转换得:
给了 (n(n le 5 imes 10^5)) 条线段,求覆盖 ([1..n]) 需要的最少条数
分析
设 (f_i) 表示覆盖了 ([1..n]) 时需要的最少的线段数
那么 (O(n^2)) 的转移是这样的
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 5e5 + 5;
int n , a[N] , f[N];
int main()
{
scanf("%d" , &n);
for(register int i = 1; i <= n; i++) scanf("%d" , a + i) , f[i] = N;
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= n; j++)
{
int l = max(j - a[j] , 1) , r = min(j + a[j] , n);
if (l <= i && i <= r) f[i] = min(f[i] , f[l - 1] + 1);
}
printf("%d" , f[n]);
}
而我们发现在转移时,(f_i) 的要取所有满足条件的线段的 (f_{l-1}) 的最小值
而要满足的条件就是 (l leq i leq r)
于是我们用线段树维护
逆着考虑,维护每个 (f_i) 能影响的范围
#include<cstdio>
#include<iostream>
#include<cstring>
#define ls (k << 1)
#define rs (ls | 1)
using namespace std;
const int N = 5e5 + 5 , INF = 0x3f3f3f3f;
int n , f[N] , nxt[N] , seg[N * 4] , tag[N * 4];
struct node{
int l , r;
}a[N];
void pushdown(int k)
{
if (tag[k] == INF) return;
seg[ls] = min(seg[ls] , tag[k]) , tag[ls] = min(tag[ls] , tag[k]);
seg[rs] = min(seg[rs] , tag[k]) , tag[rs] = min(tag[rs] , tag[k]);
tag[k] = INF;
}
void update(int l , int r , int k , int tl , int tr , int v)
{
if (tl <= l && r <= tr)
{
seg[k] = min(seg[k] , v) , tag[k] = min(tag[k] , v);
return;
}
pushdown(k);
int mid = (l + r) >> 1;
if (tl <= mid) update(l , mid , ls , tl , tr , v);
if (tr > mid) update(mid + 1 , r , rs , tl , tr , v);
seg[k] = min(seg[ls] , seg[rs]);
}
int query(int l , int r , int k , int x)
{
if (l == r && l == x) return seg[k];
pushdown(k);
int mid = (l + r) >> 1;
if (x <= mid) return query(l , mid , ls , x);
if (x > mid) return query(mid + 1 , r , rs , x);
}
int main()
{
scanf("%d" , &n);
int x;
for(register int i = 1; i <= n; i++)
{
scanf("%d" , &x);
a[i].l = max(i - x , 1) , a[i].r = min(i + x , n);
if (a[nxt[a[i].l - 1]].r < a[i].r) nxt[a[i].l - 1] = i;
}
memset(seg , 0x3f3f3f3f , sizeof seg) , memset(tag , 0x3f3f3f3f , sizeof tag);
if (nxt[0] != 0) update(1 , n , 1 , a[nxt[0]].l , a[nxt[0]].r , 0);
for(register int i = 1; i <= n; i++)
{
f[i] = query(1 , n , 1 , i) + 1;
if (nxt[i] != 0) update(1 , n , 1 , a[nxt[i]].l , a[nxt[i]].r , f[i]);
}
printf("%d" , f[n]);
}