萌新刚学 OI 114514 秒，求助
  • 板块学术版
  • 楼主lingfunny
  • 当前回复15
  • 已保存回复15
  • 发布时间2022/12/2 10:28
  • 上次更新2023/10/27 00:46:22
查看原帖
萌新刚学 OI 114514 秒，求助
280800
lingfunny楼主2022/12/2 10:28

从 nn 个物品中，选两个物品 A,BA, B，求如下分式极值：

f(A)+f(B)g(A)+g(B)\frac{f(A)+f(B)}{g(A)+g(B)}

理论上应该算是一类分数规划问题，不过我没怎么了解过，似乎有低于 O(n2)O(n^2) 做法。

但如果是这样的分式呢：

f(A)+f(B)g(A)+g(B)+h(A)h(B)\frac{f(A)+f(B)}{g(A)+g(B)+h(A)h(B)}

是否还有低于 O(n2)O(n^2) 的做法？

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

2022/12/2 10:28