P9100 [PA 2020] Miny 题解
xiaoniu142857
·
·
题解
这道题难点在于状态设计。考虑线性 DP，设 dp_i 为仅考虑前 i 个地雷且钦定第 i 个不引爆的方案数。这样设计的好处在于 i 前面的地雷一定不会引爆 i 后面的，从而满足无后效性。
注意需要在左右无穷远处各添加一个爆炸半径无穷大的哨兵地雷，下标分别为 0 和 n+1，确保哨兵能引爆所有地雷。答案即为 dp_{n+1}。
然后考虑转移。对于每个 i，枚举所有 j<i，然后判断引爆 [j+1,i-1] 中所有地雷是否会引爆 i 或 j。若均不会则能转移，令 dp_i\leftarrow dp_i+dp_j。
尝试转化这个条件。设 l_i 为 i 左边第一个会引爆 i 的地雷，r_i 同理。则上述条件等价于 j\ge l_i 且 i\le r_j。
然后状态转移方程如下。
$$
\begin{aligned}
dp_i&=\sum_{j=l_i}^{i-1}[i\le r_j]\cdot dp_j\\
&=\sum_{j=0}^{i-1}[i\le r_j]\cdot dp_j-\sum_{j=0}^{l_i-1}[i\le r_j]\cdot dp_j\\
\end{aligned}
$$
先离线，把 $dp_i$ 的两个询问分别挂在 $i-1$ 和 $l_i-1$ 上，然后树状数组扫一遍即可。需要特殊处理 $j=0$ 的情况。
时间复杂度 $O(n\log n)$。
```cpp
#include <bits/stdc++.h>
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define lowbit(x) ((x)&-(x))
#define eb emplace_back
#define int long long
using namespace std;
constexpr int N=3e5+5,P=1e9+7,INF=3e18;
struct item{
int p,rad,lb,rb;
}a[N];
struct query{
query()=default;
query(int _id,int _k):id(_id),k(_k){}
int id,k;
};
int dp[N],st[N],l[N],r[N],s[N],n,top;
vector<query> q[N];
void add(int p,int x){while(p<=n+1) s[p]+=x,p+=lowbit(p);}
int ask(int p){
int res=0;
while(p) res+=s[p],p^=lowbit(p);
return res;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;
a[0]={-INF,INF,-INF,INF};
a[n+1]={INF,INF,-INF,INF};
r[0]=r[n+1]=n+1;
dp[0]=1;
rept(i,1,n){
cin>>a[i].p>>a[i].rad;
a[i].lb=a[i].p-a[i].rad;
a[i].rb=a[i].p+a[i].rad;
}
st[top=1]=0;
rept(i,1,n){
int L=1,R=top,mid;
while(L<R){
mid=L+R+1>>1;
a[st[mid]].rb>=a[i].p?L=mid:R=mid-1;
}
l[i]=st[L];
while(a[st[top]].rb<a[i].rb) --top;
st[++top]=i;
}
st[top=1]=n+1;
pert(i,n,1){
int L=1,R=top,mid;
while(L<R){
mid=L+R+1>>1;
a[st[mid]].lb<=a[i].p?L=mid:R=mid-1;
}
r[i]=st[L];
while(a[st[top]].lb>a[i].lb) --top;
st[++top]=i;
}
rept(i,1,n+1){
if(!l[i]) ++l[i],++dp[i]; // 特判从dp[0]转移
if(l[i]>1) q[l[i]-1].eb(i,-1);
if(i>1) q[i-1].eb(i,1);
}
rept(i,1,n+1){
add(r[i],dp[i]);
for(auto [id,k]:q[i]){
(dp[id]+=k*(ask(n+1)-ask(id-1)))%=P;
}
}
cout<<(dp[n+1]+P)%P;
return 0;
}
```