洛谷 P9100 [PA 2020] Miny 题解

这道题难点在于状态设计。考虑线性 DP，设 \(dp_i\) 为仅考虑前 \(i\) 个地雷且钦定第 \(i\) 个不引爆的方案数。这样设计的好处在于 \(i\) 前面的地雷一定不会引爆 \(i\) 后面的，从而满足无后效性。
注意需要在左右无穷远处各添加一个爆炸半径无穷大的哨兵地雷，下标分别为 \(0\) 和 \(n+1\)，确保哨兵能引爆所有地雷。答案即为 \(dp_{n+1}\)。

然后考虑转移。对于每个 \(i\)，枚举所有 \(j>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.p>>a.rad;        a.lb=a.p-a.rad;        a.rb=a.p+a.rad;    }    st[top=1]=0;    rept(i,1,n){        int L=1,R=top,mid;        while(L>1;            a[st[mid]].rb>=a.p?L=mid:R=mid-1;        }        l=st[L];        while(a[st[top]].rb>1;            a[st[mid]].lba.lb) --top;        st[++top]=i;    }    rept(i,1,n+1){        if(!l) ++l,++dp;  // 特判从dp[0]转移        if(l>1) q[l-1].eb(i,-1);        if(i>1) q[i-1].eb(i,1);    }    rept(i,1,n+1){        add(r,dp);        for(auto [id,k]:q){            (dp[id]+=k*(ask(n+1)-ask(id-1)))%=P;        }    }    cout

用心讨论，共获提升！