题目

实际上经转换得：

给了 \(n(n \le 5 \times 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]);

}

巴特西

JZOJ 捕老鼠

题目

分析

最新文章

热门文章