题解P3062【[USACO14JAN]Cross Country Skiing S】

信守天下 · 2021-08-10 15:28:45 · 题解

洛谷传送门

思路 1：贪心

我们可以记录上一个建信号塔的位置 l。

对于一个点 r：

在 l 和 r 之间建信号塔的代价低于在 r 建 1 个新信号塔的代价时。

选择在中间建信号塔。

否则计算从 l 到 r - 1 所需代价，累加答案，再移动 l 到 r。

时间复杂度

排序 O(n \log n)。

求解 O(n)。

共 O(n \log n)。

贪心 code

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int kMaxN = 2001;
int n, a, b;
double ans;
int cow[kMaxN];
int main() {
  cin >> n >> a >> b;
  for (int i = 1; i <= n; i++) {
    cin >> cow[i];
  }
  sort(cow + 1, cow + 1 + n);
  double num = a;                        //当前费用
  for (int i = 1, j = 2; j <= n; j++) {  //左边界,右边界
    if (num <= (cow[j] - cow[i]) * 1.0 * b / 2) {
      i = j;       //移动边界
      ans += num;  //累加答案
      num = a;
    } else {
      num = a + (cow[j] - cow[i]) * 1.0 * b / 2;
    }
  }
  ans += num;
  if (abs((int)ans - ans) <= 1e-5) {  //注意精度误差
    printf("%d", (int)ans);
  } else {
    printf("%.1f", ans);
  }
  return 0;
}

思路 2：动态规划

由于区间总是覆盖连续的一段，所以我们先将点按照坐标排序。

然后可以考虑按顺序进行覆盖，由此得到状态可以使用的拓扑序。

考虑用动态规划求解。

用当前覆盖到的点、当前总代价作为状态，其中总代价是最优化属性。

枚举下一个区间的右边界是转移，左边界就是下一个要覆盖的点。

时间复杂度

状态数量 O(n)。

每个状态的转移数量 O(n)。

总共 O(n^2)。

动态规划 code

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

using namespace std;

const int kMaxN = 2001;

int p[kMaxN], dp[kMaxN];
int n, a, b;

int main() {
  cin >> n >> a >> b;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
  }
  sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; i++) {                                  // 枚举阶段
    dp[i] = 0x7fffffff;                                           // 初始化答案
    for (int j = 1; j <= i; j++) {                                // 枚举当前段左边界
      dp[i] = min(dp[i], dp[j - 1] + (p[i] - p[j]) * b + 2 * a);  // 计算代价更新答案
    }
  }
  cout << dp[n] / 2 << (dp[n] % 2 ? ".5" : "");  // 有小数则输出
  return 0;
}