P3062

Parat_rooper · 2021-08-17 09:40:26 · 题解

解题思路：

首先观察题面，不难发现，对于任意一段区间 [i, j]，若已知 [1, i-1] 都被覆盖的最小代价时，是可以直接求出覆盖 [1, j] 的最小代价的。所以我们不难想到区间动态规划，而这题很明显可以用到收集型的优化。

于是我们令 cost_i 表示以 i 结尾的区间的最小代价，而 f_{i ,j} 表示以区间 [1, i] 从 j 断开，分成 [1, j - 1] 和 [j, i] 两个区间，我们可以写出状态转移方程：

此处 money_{j, i} 算的是在区间 [i, j] 中放一个信号发射器的最小代价。然后根据这个转移方程我们就可以写出代码了。

代码如下

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int kMaxN = 2001;

int n, w[kMaxN], f[kMaxN][kMaxN], cost[kMaxN], a, b;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
  cin >> n >> a >> b;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    cost[i] = (1e9 + 1);//cost计算[1,i]的最小代价
  }
  sort(w + 1, w + n + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      f[j][i] = cost[j - 1] + (w[i] - w[j]) * b + 2 * a;
      cost[i] = min(cost[i], f[j][i]);
    }
  }
  if (cost[n] % 2) {
    cout << cost[n] / 2 << ".5";
  } else {
      cout << cost[n] / 2;
  }
  return 0;
}

虽然这一段代码也能通过，但经过我反复的 看题解 推敲后，我想到了优化状态的方式。

我们发现实际上 f 数组是废的，我们可以直接删掉，因为我们只需要求所有的可以表示为 [1, i] 的区间，而 f 数组也是同样的作用，因此此时我们的状态转移方程可以简化为：