关于dp斜率优化符号问题
  • 板块学术版
  • 楼主LYR_
  • 当前回复16
  • 已保存回复16
  • 发布时间2022/8/17 21:59
  • 上次更新2023/10/27 14:51:54
查看原帖
关于dp斜率优化符号问题
110319
LYR_楼主2022/8/17 21:59

两个while里的 >=<= 换成 >< 会出错吗?

int l = 1, r = 0;
for (int j = 1; j <= n; j++) {
	P p = P(2 * a[j], a[j] * a[j] + f[i - 1][j - 1]);
	while (l < r && (sk[r].se - sk[r - 1].se) * (p.fi - sk[r].fi) >= (p.se - sk[r].se) * (sk[r].fi - sk[r - 1].fi)) r--;
   sk[++r] = p;
   while (l < r && (sk[l + 1].se - sk[l].se) <= a[j] * (sk[l + 1].fi - sk[l].fi)) l++;
   f[i][j] = sk[l].fi * (-a[j]) + sk[l].se + a[j] * a[j];
}
2022/8/17 21:59
加载中...