先读题。最小建设费用最大，有点绕。不会做。

那我们先试着简化一下题目，然后看能不能从简化后的题目中，分析出一些有用的结论，再利用这些结论去解决原来的题目。

如果已经确定了这 m 个公司，那么怎么建基站，才能使建设费用最小？

一眼 O(m^2) 的 DP。想法太简单，以致于没什么用。再仔细分析一下下。

如果只有两家公司，那么我们应该建一个还是两个？位置记为 x1, x2，那么建一个的代价是 A+B(x2-x1)/2，建两个的代价是 2A。那么如果 (x2-x1)>2B/A，建两个的代价更小；反之建一个的代价更小。

再考虑更通常的情况下：我们现在有两个基站，覆盖范围分别为 [l1, r1] 和 [l2, r2]，那么是否应该合并成一个基站？类似上面的做法，分别算一下建两个基站的代价和合并成一个的代价，再比较一下。我们会得出相似的结论：如果 (l2-r1) > 2B/A，建两个的代价更小；相反的话，建一个的代价更小。

那么这个简化版的题目就可以很简单地解决了：最小费用的建设方案应该是，距离小于等于2B/A的相邻点在同一个基站下，距离大于2B/A的相邻点应该处在不同的基站。

这个东西有什么用？可以用来状态转移！！！

用 dp[i] 表示确定了 i 家公司的建设费用，那么 dp[i+1] = dp[i] + cost(i, i+1)。cost(i, i+1) 就可以根据上面结论去计算。也就是：如果第 i+1 家公司和第 i 家公司坐标相差大于 2B/A，则新建一个基站，否则将 i 家公司所在的基站扩大，把第 i+1家公司包含进来。

再回到原题目，我们就只需要根据题意，将状态表示清楚，写明白状态转移方程，再加一点点优化，这道题就解决了。

先排序。

然后 dp[i][j] 表示从 1~j 家公司中选择了i家公司，且第j家公司必选的最小建设费用的最大值。好像还是有点绕。把最小建设费用替换成代价。代价最大值，那不是从所有子状态里取个max就行了？那最小建设费用体现在哪里？就是上面的 状态转移cost。

那么状态转移方程：

  • 当 a[j] - a[k] > 2B/A 时，dp[i][j] = max(dp[i][j], dp[i - 1][k] + A) （新建一个基站）
  • 当 a[j] - a[k] <= 2B/A 时，dp[i][j] = max(dp[i][j], dp[i - 1][k] + B * (a[j] - a[k]) / 2) （扩展前一个基站）

枚举 i,j,k，O(n^3) DP，做完了

再利用单调性稍微优化一下，复杂度就可以降到 O(n^2)。

记p为满足 a[j] - a[k] <= 2B/A 的最小值。对 dp[i][j] 来说， k 在 [1,p-1] 里，是第一个转移方程。k 在 [p, j-1] 里， 是第二个转移方程。 两个转移方程都是区间求max。

  • max(dp[i - 1][k]) + A
  • max(dp[i - 1][k] - B * a[k] / 2) + B * a[j] + 2

如果从1~n枚举j的话，k单调非降。那么第一个转移方程的区间求max，可以直接前缀更新。第二个转移方程的区间求max，可以利用单调队列优化。均摊复杂度 O(1)，整体复杂度 O(n^2)。

  #include <bits/stdc++.h>
  using namespace std;
  const int N = 5000 + 5;

  int n, m, A, B;
  int a[N];
  double dp[N][N];

  int main() {
      ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
      cin >> n >> m >> A >> B;
      for(int i = 1; i <= n; i++) cin >> a[i];
      sort(a + 1, a + n + 1);
      for(int i = 1; i <= m; i++) {
          deque<pair<double, int>> dq;
          int p = i - 1;
          double ma = 0.0;
          dq.push_back({dp[i - 1][i - 1] - a[i - 1] * B / 2.0, i - 1});
          for(int j = i; j <= n; j++) {
              while((a[j] - a[p]) * B >= 2 * A) {
                  ma = max(ma, dp[i - 1][p]);
                  p++;
              }
              dp[i][j] = max(dp[i][j], ma + A);
              while(!dq.empty() && dq.front().second < p) dq.pop_front();
              if(!dq.empty()) dp[i][j] = max(dp[i][j], dq.front().first + 1.0 * a[j] * B / 2.0);
              pair<double, int> pr = {dp[i - 1][j] - a[j] * B / 2.0, j};
              while(!dq.empty() && dq.back().first < pr.first) dq.pop_back();
              dq.push_back(pr);
          }
      }
      double ans = 0.0;
      for(int i = m; i <= n; i++) ans = max(ans, dp[m][i]);
      cout << std::fixed << std::setprecision(1) << ans << endl;
      return 0;
  }