题目思路

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

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

代码

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] x = new int[n];
        int[] a = new int[n];
        double[][] f = new double[n][n];
        double[][] g = new double[n][n];

        for (int i = 0; i < n; i++) {
            x[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < i; j++) {
                f[i][j] = 1.0 * (a[0] + a[j]) / (x[j] - x[0]) * (a[j] + a[i]) / (x[i] - x[j]);
            }
        }

        for (int i = n - 2; i > 0; i--) {
            for (int j = i + 1; j < n - 1; j++) {
                g[i][j] = 1.0 * (a[n - 1] + a[j]) / (x[n - 1] - x[j]) * (a[j] + a[i]) / (x[j] - x[i]);
            }
        }

        double ans = 0;
        for (int i = 2; i < n - 2; i++) {
            double l = 0, r = 0;
            for (int j = 1; j < i; j++)
                l = Math.max(l, f[i][j]);
            for (int j = i + 1; j < n - 1; j++)
                r = Math.max(r, g[i][j]);
            ans = Math.max(ans, l * r);
        }

        System.out.printf("%.9f\n", ans);
    }
}

C++

#include <bits/stdc++.h>

using namespace std;

signed main()
{
  int n;
  cin >> n;
  vector<int> x(n), a(n);
  vector<vector<double>> f(n, vector<double>(n, 0)), g = f;
  for (int i = 0; i < n; i++)
    cin >> x[i];
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 1; i < n - 1; i++) {
    for (int j = 1; j < i; j++) {
      f[i][j] = 1.0 * (a[0] + a[j]) / (x[j] - x[0]) * (a[j] + a[i]) / (x[i] - x[j]);
    }
  }
  for (int i = n - 2; i > 0;-- i) {
    for (int j = i + 1;j < n - 1; j++) {
      g[i][j] = 1.0 * (a[n - 1] + a[j]) / (x[n - 1] - x[j]) * (a[j] + a[i]) / (x[j] - x[i]);
    }
  }
  double ans = 0;
  for (int i = 2; i < n - 2;++ i) {
    double l = 0, r = 0;
    for (int j = 1; j < i;++ j)
      l = max(l, f[i][j]);
    for (int j = i + 1; j < n - 1;++ j)
      r = max(r, g[i][j]);
    ans = max(ans, l * r);
  }
  printf("%.9lf\n", ans);
}

Python

n = int(input())
x = list(map(int, input().split()))
a = list(map(int, input().split()))

f = [[0] * n for _ in range(n)]
g = [[0] * n for _ in range(n)]

for i in range(1, n - 1):
    for j in range(1, i):
        f[i][j] = (a[0] + a[j]) / (x[j] - x[0]) * (a[j] + a[i]) / (x[i] - x[j])

for i in range(n - 2, 0, -1):
    for j in range(i + 1, n - 1):
        g[i][j] = (a[n - 1] + a[j]) / (x[n - 1] - x[j]) * (a[j] + a[i]) / (x[j] - x[i])

ans = 0
for i in range(2, n - 2):
    l = max(f[i][:i])
    r = max(g[i][i+1:])
    ans = max(ans, l * r)

print("{:.9f}".format(ans))

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

在直线上有$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
可以证明，这样设置信号站是最优的。