关于斜率优化dp中删队尾的操作疑问
  • 板块学术版
  • 楼主Fireworks_Rise
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/2/2 20:37
  • 上次更新2025/2/3 11:19:13
查看原帖
关于斜率优化dp中删队尾的操作疑问
970993
Fireworks_Rise楼主2025/2/2 20:37

在判断处理删除队尾点的时候(以下凸包为例),有下面两种写法:

写法 11

while(head<tail&&slope(q[tail],q[tail-1])>=slope(i,q[tail]))
	--tail;

写法 22

while(head<tail&&slope(q[tail],q[tail-1])>=slope(i,q[tail-1]))
	--tail;

(这里的 slope 是求斜率的自定义函数,qq 是队列,headheadtailtail 分别为队头和队尾)

按道理来说,感觉两种都可以啊,而且画了大半天图,都没能想出反例(有可能是我太菜了)。

对于 [HNOI2008] 玩具装箱 这题,两种写法都可以过去,但是在 百日旅行 这题的斜率优化做法中写法 22 不能过掉所有的数据。

本校大佬持很多不同观点,还有巨佬表示是精度问题(不知道是否正确)。

求对于写法 22 错误性的证明或推倒qwq。

2025/2/2 20:37
加载中...