BZOJ5017炸弹题解--玄学递推

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=5017

分析

老师讲课谈到了这道题，课上想出了个连边建图然后乱搞的操作，被老师钦定的递推方法枪毙了；
晚上回去做了做，好像复杂度是不对。还是学习了下此题递推方法，感觉考场上写这个的是抱着得部分分的心理A了这道题(话说洛谷没有SNOI2017的题目

我们用$l[i],r[i]$表示$i$最左和最右能拓展到的炸弹编号,初始化$l[i]=r[i]=i$,$rr[i]$表示$i$最大的爆炸半径(因为它可能会随着$l[i],r[i]$更新而更新)

然后就递推了.求$l[i]$,如果$x[i]-x[l[i]-1]<=rr[i]$则拓展，同时检查是否更新$rr[i]$;求$r[i]$类似。

时间复杂度我也很懵，感觉应该有个均摊值,老师课上讲拓展次数不会超过$log N$感觉不太对啊。。。

同时这题有个线段树优化建边+Tarjan缩点+拓扑排序后DP的方法

注意

$l[i]$是向左拓展,故从$1$递推到$N$;

$r[i]$就要从$N$递推到$1$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#define ll long long 
#define ri register int 
using namespace std;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;
	return ;
}
const int maxn=500000;
const int inf=0x7fffffff;
int n;
ll l[maxn],r[maxn],x[maxn],rr[maxn];
ll ans=0;
int main(){
	read(n);
	for(ri i=1;i<=n;i++){
		read(x[i]),read(rr[i]);
		l[i]=r[i]=i;
	}
	for(ri i=1;i<=n;i++){
		while(l[i]>1&&x[i]-x[l[i]-1]<=rr[i]){
			l[i]=l[l[i]-1],rr[i]=max(rr[i],rr[l[i]]-(x[i]-x[l[i]]));
	    }
	}
	for(ri i=n;i>=1;i--){
		while(r[i]<n&&x[r[i]+1]-x[i]<=rr[i]){
			r[i]=r[r[i]+1],l[i]=min(l[i],l[r[i]]);
		}
		ans=(ans+1ll*i*(r[i]-l[i]+1))%1000000007;
    }
    printf("%lld\n",ans);
	return 0;
}

推荐学习博客

https://blog.csdn.net/c_k_y_/article/details/79980119

https://blog.csdn.net/Icefox_zhx/article/details/78877188