求助:关于斜率优化在横坐标相同时的特判
  • 板块学术版
  • 楼主Rem_CandleFire
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/10/31 09:38
  • 上次更新2024/10/31 16:31:08
查看原帖
求助:关于斜率优化在横坐标相同时的特判
421421
Rem_CandleFire楼主2024/10/31 09:38

我们以 fi=min{fj+ai×bj}f_i=\min\{f_j+a_i\times b_j\} 为例。求斜率时的代码形如:

double Slope(int a,int b)
{
	double y=...;
	double x=...;
	if(x==0) return ?;
	return y/x;
}

仓库建设 中,如果 ?=inf=inf,那么会被讨论区的数据 hack 掉,所以改成了 if(x==0) return y>0 ? inf : -inf 这样可以通过。

中间做的几道题都不存在 x=0 的情况。然而在 丝之割 一题中按上述方式写会无法通过,有 hack:

6 6
813 396 347 787 932 101 
121 260 577 873 120 286 
2 1
2 2
5 5
5 4
6 5
5 3

ans: 196802

看题解之后发现写成 if(x==0) return inf; 就过了。

于是请问这两种情况有什么区别,或者说对于这类型的特判有什么需要注意的。(需要提供其它,例如完整代码等请at)

2024/10/31 09:38
加载中...