题目思路

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

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

代码

Java

题目描述

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

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

输入描述

第一行输入一个正整数$n$，代表可以建立站的位置数量。

第二行输入$n$个正整数$x_i$，，代表每个位置的坐标。

第三行输入$n$个正整数$a_i$，代表每个位置建立基站时的设施强度。

$5\le n\le 2000$

$1\le x_i,a_i\le 10^4$

保证$x_i$是升序的，即$x_1<x_2<...<x_n$

输出描述

一个浮点数，代表最终信号强度的最大值。如果你的答案和标准答案的相对误差不超过$10^{-6}$，则认为你的答案正确。

样例

输入

6
1 3 5 7 8 10
7 6 9 5 1 3

输出

910.0000000000

说明

选择第 1、2、3、4、6 这五个位置建立信号站。第一个位置发射出一个强度为1的信号，到达第二个位置时，信号强度变成
6.5.
到达第三个位置时，信号强度变成 48.75
到达第四个位置时，信号强度变成 341.25
到达第六个位置时，信号强度变成 910
可以证明，这样设置信号站是最优的。