题目描述

在直线上有$n$个建立基站的位置。现在需要建立5个基站来传递信号。已知两个基站之间传递信号会发生信号强度的变化，传递的信号强度和两个基站的设施强度之和成正比，和两个基站的距离成反比。举个例子，若两个基站的设施强度分别为$a$和$b$，他们的距离为$d$，那么一个强度为的信号传递后会变成$x*(a+b)/d$

现在给定了这几个位置的坐标$x_i$，，以及在该位置建立基站的设施强度$a_i$，第1个和第$n$个位置是必须建立基站的。也就是说还需要再建立3个基站。请你计算如何建立这三个基站，可以使得从最左边的信号传递到最右边时，信号强度是最高的?假设左边发出的信号初始强度为 1。请注意信号不能跳跃传递，也就是说，必须从左到右，1->2->3->4->5 这样传递。

题目思路

思维题，如果直接枚举选三个基站会超时，我们可以先枚举前两个基站的传递强度放到f中，并枚举后两个基站的传递强度放到g中。然后对于枚举所有的中间基站i，取f[i][j]的最大值和g[i][j]的最大值进行累乘即是这个点作为中间基站的所有情况的最大值。

枚举所有中间基站取最大的那个即可，时间复杂度：$O(n^2)$

代码

Java