洛谷 P9100 [PA 2020] Miny 题解
这道题难点在于状态设计。考虑线性 DP，设d p i dp_idpi为仅考虑前i ii个地雷且钦定第i ii个不引爆的方案数。这样设计的好处在于i ii前面的地雷一定不会引爆i ii后面的，从而满足无后效性。
注意需要在左右无穷远处各添加一个爆炸半径无穷大的哨兵地雷，下标分别为0 00和n + 1 n+1n+1，确保哨兵能引爆所有地雷。答案即为d p n + 1 dp_{n+1}dpn+1。
然后考虑转移。对于每个i ii，枚举所有j < i j<ij<i，然后判断引爆[ j + 1 , i − 1 ] [j+1,i-1][j+1,i−1]中所有地雷是否会引爆i ii或j jj。若均不会则能转移，令d p i ← d p i + d p j dp_i\leftarrow dp_i+dp_jdpi←dpi+dpj。
尝试转化这个条件。设l i l_ili为i ii左边第一个会引爆i ii的地雷，r i r_iri同理。则上述条件等价于j ≥ l i j\ge l_ij≥li且i ≤ r j i\le r_ji≤rj。
l , r l,rl,r两个数组都可以单调栈上二分处理。
然后状态转移方程如下。
d p i = ∑ j = l i i − 1 [ i ≤ r j ] ⋅ d p j = ∑ j = 0 i − 1 [ i ≤ r j ] ⋅ d p j − ∑ j = 0 l i − 1 [ i ≤ r j ] ⋅ d p 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}dpi=j=li∑i−1[i≤rj]⋅dpj=j=0∑i−1[i≤rj]⋅dpj−j=0∑li−1[i≤rj]⋅dpj
先离线，把d p i dp_idpi的两个询问分别挂在i − 1 i-1i−1和l i − 1 l_i-1li−1上，然后树状数组扫一遍即可。需要特殊处理j = 0 j=0j=0的情况。
时间复杂度O ( n log n ) O(n\log n)O(nlogn)。
#include<bits/stdc++.h>#definerept(i,a,b)for(inti(a);i<=b;++i)#definepert(i,a,b)for(inti(a);i>=b;--i)#definelowbit(x)((x)&-(x))#defineebemplace_back#defineintlonglongusingnamespacestd;constexprintN=3e5+5,P=1e9+7,INF=3e18;structitem{intp,rad,lb,rb;}a[N];structquery{query()=default;query(int_id,int_k):id(_id),k(_k){}intid,k;};intdp[N],st[N],l[N],r[N],s[N],n,top;vector<query>q[N];voidadd(intp,intx){while(p<=n+1)s[p]+=x,p+=lowbit(p);}intask(intp){intres=0;while(p)res+=s[p],p^=lowbit(p);returnres;}signedmain(){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){intL=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){intL=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;return0;}