摹熹 发表于 2026-1-27 01:00:09

洛谷 P9100 [PA 2020] Miny 题解

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

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

僻嘶 发表于 2026-1-29 09:23:12

用心讨论，共获提升！

呈步 发表于 2026-2-8 05:45:38

鼓励转贴优秀软件安全工具和文档！

申倩语 发表于 2026-2-8 06:26:37

收藏一下   不知道什么时候能用到

轮达 发表于 2026-2-8 07:51:59

谢谢分享，辛苦了

呼延含玉 发表于 2026-2-9 11:38:46

感谢分享，学习下。

奄蜊 发表于 2026-2-9 16:47:46

懂技术并乐意极积无私分享的人越来越少。珍惜

荏牌 发表于 2026-2-10 22:05:11

不错，里面软件多更新就更好了

唐茗 发表于 2026-2-12 08:06:02

过来提前占个楼

喳谍 发表于 2026-2-12 09:05:49

鼓励转贴优秀软件安全工具和文档！

揭荸 发表于 2026-2-13 10:36:33

懂技术并乐意极积无私分享的人越来越少。珍惜

赘暨逢 发表于 2026-2-13 14:01:41

热心回复！

吕颐然 发表于 2026-2-13 18:31:51

这个好，看起来很实用

菅舛 发表于 2026-2-13 20:50:21

这个有用。

忙贬 发表于 2026-2-13 21:28:11

鼓励转贴优秀软件安全工具和文档！

坐褐 发表于 2026-2-24 06:21:13

感谢分享，下载保存了，貌似很强大

兜蛇 发表于 2026-2-27 13:34:02

感谢分享，下载保存了，貌似很强大

韶侪 发表于 2026-2-27 15:01:50

谢谢分享，辛苦了

频鹏凶 发表于 2026-3-6 23:37:30

感谢分享，学习下。

昝沛珊 发表于 2026-3-9 19:06:23

yyds。多谢分享
页: [1] 2
查看完整版本: 洛谷 P9100 [PA 2020] Miny 题解