【蒟蒻的yy】有关三维斜率dp
  • 板块学术版
  • 楼主Graygoo
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/5/20 22:39
  • 上次更新2023/10/28 01:01:08
查看原帖
【蒟蒻的yy】有关三维斜率dp
535714
Graygoo楼主2022/5/20 22:39

众所周知,斜率dp能优化

dp[i]=min dp[j]+c[i]c[j]dp[i] =min\space{dp[j] + c[i] * c[j]} 这一类的转移方程,那么如果转移方程变为dp[i]=min dp[j]+c[i]c[j]+d[i]d[j]dp[i] =min\space{dp[j] + c[i] * c[j]} + d[i]*d[j]这样的话,是否能够在三维空间内维护一组平面构成的凸包来实现优化呢

2022/5/20 22:39
加载中...