P3406. 海底高铁

发表于 分类于 阅读次数： Waline： 本文字数： 186 阅读时长 ≈ 1 分钟

考点

  • 差分

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
typedef long long ll;
int n, m, b[maxn], diff[maxn], pre[maxn];

struct node {
  int a_, b_, c_;
} a[maxn];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) cin >> b[i];
  for (int i = 1; i < n; ++i) cin >> a[i].a_ >> a[i].b_ >> a[i].c_;
  for (int i = 1; i < m; ++i) {
    int mi = min(b[i], b[i + 1]), mx = max(b[i], b[i + 1]);
    ++diff[mi], --diff[mx];
  }
  ll ans = 0;
  for (int i = 1; i < n; ++i) {
    diff[i] += diff[i - 1];
    ans += min(1ll * a[i].a_ * diff[i], (a[i].c_ + 1ll * a[i].b_ * diff[i]));
  }
  cout << ans;
  return 0;
}

思路

从i到i + 1的最低开销应该等于\(\min \left( cnt_i\times a_i,c_i+cnt_i\times b_i \right)\)，

其中\(cnt_i\)代表i到i + 1的次数。

直接用差分进行区间修改即可。