洛谷 P9100 [PA 2020] Miny 题解

这道题难点在于状态设计。考虑线性 DP设d p i dp_idpi​为仅考虑前i ii个地雷且钦定第i ii个不引爆的方案数。这样设计的好处在于i ii前面的地雷一定不会引爆i ii后面的从而满足无后效性。注意需要在左右无穷远处各添加一个爆炸半径无穷大的哨兵地雷下标分别为0 00和n 1 n1n1确保哨兵能引爆所有地雷。答案即为d p n 1 dp_{n1}dpn1​。然后考虑转移。对于每个i ii枚举所有j i jiji然后判断引爆[ j 1 , i − 1 ] [j1,i-1][j1,i−1]中所有地雷是否会引爆i ii或j jj。若均不会则能转移令d p i ← d p i d p j dp_i\leftarrow dp_idp_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_{jl_i}^{i-1}[i\le r_j]\cdot dp_j\\ \sum_{j0}^{i-1}[i\le r_j]\cdot dp_j-\sum_{j0}^{l_i-1}[i\le r_j]\cdot dp_j\\ \end{aligned}dpi​​jli​∑i−1​[i≤rj​]⋅dpj​j0∑i−1​[i≤rj​]⋅dpj​−j0∑li​−1​[i≤rj​]⋅dpj​​先离线把d p i dp_idpi​的两个询问分别挂在i − 1 i-1i−1和l i − 1 l_i-1li​−1上然后树状数组扫一遍即可。需要特殊处理j 0 j0j0的情况。时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)。#includebits/stdc.h#definerept(i,a,b)for(inti(a);ib;i)#definepert(i,a,b)for(inti(a);ib;--i)#definelowbit(x)((x)-(x))#defineebemplace_back#defineintlonglongusingnamespacestd;constexprintN3e55,P1e97,INF3e18;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;vectorqueryq[N];voidadd(intp,intx){while(pn1)s[p]x,plowbit(p);}intask(intp){intres0;while(p)ress[p],p^lowbit(p);returnres;}signedmain(){cin.tie(0)-sync_with_stdio(0);cinn;a[0]{-INF,INF,-INF,INF};a[n1]{INF,INF,-INF,INF};r[0]r[n1]n1;dp[0]1;rept(i,1,n){cina[i].pa[i].rad;a[i].lba[i].p-a[i].rad;a[i].rba[i].pa[i].rad;}st[top1]0;rept(i,1,n){intL1,Rtop,mid;while(LR){midLR11;a[st[mid]].rba[i].p?Lmid:Rmid-1;}l[i]st[L];while(a[st[top]].rba[i].rb)--top;st[top]i;}st[top1]n1;pert(i,n,1){intL1,Rtop,mid;while(LR){midLR11;a[st[mid]].lba[i].p?Lmid:Rmid-1;}r[i]st[L];while(a[st[top]].lba[i].lb)--top;st[top]i;}rept(i,1,n1){if(!l[i])l[i],dp[i];// 特判从dp[0]转移if(l[i]1)q[l[i]-1].eb(i,-1);if(i1)q[i-1].eb(i,1);}rept(i,1,n1){add(r[i],dp[i]);for(auto[id,k]:q[i]){(dp[id]k*(ask(n1)-ask(id-1)))%P;}}cout(dp[n1]P)%P;return0;}