题解：P12845 [蓝桥杯 2025 国 A] 连锁反应

· · 题解

题目

这不一眼 DP 吗？

首先求出每个炸弹引爆后的范围，细节的可以看这篇这不应该比建图什么的好想吗。

设 ql_i 表示引爆第 i 颗炸弹后最左边的被引爆的炸弹，qr_i 表示引爆第 i 颗炸弹后最右边的被引爆的炸弹。

然后更新 ql 时不断往前跳，期间更新一下 r_i。

while(ql[i]>1&&a[i].p-a[ql[i]-1].p<=a[i].l) 
  a[i].r=max(a[i].r,a[ql[i]-1].r-(a[i].p-a[ql[i]-1].p)),ql[i]=ql[ql[i]-1];

更新 qr 时同理，不断往右跳，期间可能 ql 可能会扩张，所以还要更新一下 ql。

while(qr[i]<n&&a[qr[i]+1].p-a[i].p<=a[i].r) 
  ql[i]=min(ql[i],ql[qr[i]+1]),qr[i]=qr[qr[i]+1];

而这是类似路径压缩的，时间复杂度可以看成 O(n) 的。

接下来就很简单了。

设 dp_i 表示主动引爆最少枚炸弹使得 1 到 i 的炸弹全部爆炸且没有引爆 i 之后的炸弹。

如果 i 是主动引爆的话，可以用填表法。

dp_i=\min_{j\in [ql_{i}-1,i-1]} dp_j+1

如果 i 是被引爆的话，我们可以考虑用刷表法。

dp_{qr_i}=\min_{j\in [ql_{i}-1,i-1]} dp_j+1

但这是 O(N^2) 的，可以翻转一下用树状数组维护，也可以直接线段树维护。

最后时间复杂度 O(N\log N)。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)

const int N=2e5+5,M=1e6+5;
const ll inf=1e9;
int n;
struct node{int p,l,r;}a[N];
struct BIT_mn{
    ll t[M];
    BIT_mn(){memset(t,0x3f,sizeof t);}
    void up(ll x,ll z){if(x<=0)return;for(;x<M;x+=x&-x)t[x]=min(t[x],z);}
    ll get(ll x){ ll res=1e18;for(;x;x-=x&-x)res=min(res,t[x]);return res;}
}A;
ll ql[N],qr[N];
ll dp[N];
void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i].p>>a[i].l>>a[i].r,ql[i]=qr[i]=i;
    sort(a+1,a+1+n,[](node qq,node ww){return qq.p<ww.p;});
    rep(i,2,n) while(ql[i]>1&&a[i].p-a[ql[i]-1].p<=a[i].l) a[i].r=max(a[i].r,a[ql[i]-1].r-(a[i].p-a[ql[i]-1].p)),ql[i]=ql[ql[i]-1];
    per(i,n-1,1) while(qr[i]<n&&a[qr[i]+1].p-a[i].p<=a[i].r) ql[i]=min(ql[i],ql[qr[i]+1]),qr[i]=qr[qr[i]+1];
    memset(dp,0x3f,sizeof dp);
    dp[0]=0;
    A.up(n-0+1,0);
    rep(i,1,n){
        ll v=A.get(n-(ql[i]-1)+1)+1;
        dp[i]=min(v,dp[i]);
        dp[qr[i]]=min(v,dp[qr[i]]);
        A.up(n-i+1,dp[i]);
    }
    cout<<dp[n]<<'\n';
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
}

:::