自动搬运

查看原文

来自洛谷，原作者为

	Parat_rooper **

搬运于2025-08-24 21:44:54，当前版本为作者最后更新于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]$ 两个区间，我们可以写出状态转移方程：

$$f_{i, j} = max(f_{i, j}, cost_j - 1 + money_{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 数组也是同样的作用，因此此时我们的状态转移方程可以简化为：

$$cost_i = min(cost_{j-1} + money_{i,j})$$

$money_{i, j}$ 作用同上。

最后同样记得要乘 2 处理，因为题目是要求你在答案为整数时不输出小数部分。

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

using namespace std;

const int kMaxN = 2001;

int n, w[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++) {
      cost[i] = min(cost[j - 1] + (w[i] - w[j]) * b + 2 * a, cost[i]);
    }
  }
  if (cost[n] % 2) {
    cout << cost[n] / 2 << ".5";
  } else {
      cout << cost[n] / 2;
  }
  return 0;
}

完结撒花~~~