这道题难点在于状态设计。考虑线性 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 |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
