保存帖子
发现
索引
热门
陶片放逐
关于
关于树上斜率优化
板块
学术版
楼主
konyakest
当前回复
5
已保存回复
5
发布时间
2023/8/6 22:49
上次更新
2023/11/3 05:30:09
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
关于树上斜率优化
konyakest
楼主
2023/8/6 22:49
简要：树上斜率优化可以从子树转移吗？
详细：
斜率优化是指
d
p
i
=
max
(
a
(
i
)
×
b
(
j
)
+
c
(
j
)
)
，a,b,c 可以动态求出
dp_i=\max{(a(i)\times b(j)+c(j))}\text{，a,b,c 可以动态求出}
d
p
i
=
max
(
a
(
i
)
×
b
(
j
)
+
c
(
j
))
，
a,b,c
可以动态求出
我会的树上斜率优化是指
d
p
i
=
max
j 为 i 祖先
(
a
(
i
)
×
b
(
j
)
+
c
(
j
)
)
，a,b,c 可以动态求出
dp_i=\max_{\text{j 为 i 祖先}}{(a(i)\times b(j)+c(j))}\text{，a,b,c 可以动态求出}
d
p
i
=
j
为
i
祖先
max
(
a
(
i
)
×
b
(
j
)
+
c
(
j
))
，
a,b,c
可以动态求出
请问
d
p
i
=
max
i 为 j 祖先
(
a
(
i
)
×
b
(
j
)
+
c
(
j
)
)
，a,b,c 可以动态求出
dp_i=\max_{\text{i 为 j 祖先}}{(a(i)\times b(j)+c(j))}\text{，a,b,c 可以动态求出}
d
p
i
=
i
为
j
祖先
max
(
a
(
i
)
×
b
(
j
)
+
c
(
j
))
，
a,b,c
可以动态求出
可做吗？
（目前想的是平衡树维护凸包，启发式合并）
2023/8/6 22:49
加载中...
