题解【洛谷P3406】海底高铁

题面

比较基础的前缀和+差分。

注意开\(\text{long long}\)

直接上代码吧。

#include <bits/stdc++.h>
#define itn int
#define gI gi
#define int long long

using namespace std;

typedef long long ll;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

inline ll gl()
{
    ll f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int maxn = 100003;

int n, m, cf[maxn], sum[maxn], a[maxn], b[maxn], c[maxn], ans, p[maxn];

signed main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi(), m = gi();
    for (int i = 1; i <= m; i+=1) p[i] = gi();
    for (int i = 1; i < m; i+=1)
    {
        int x = min(p[i], p[i + 1]), y = max(p[i], p[i + 1]);
        ++cf[x], --cf[y];//差分
    }
    for (int i = 1; i <= n; i+=1) sum[i] = sum[i - 1] + cf[i];//计算每一段铁路经过的次数
    for (int i = 1; i < n; i+=1)
    {
        a[i] = gi(), b[i] = gi(), c[i] = gi();
        ans += min(a[i] * sum[i], b[i] * sum[i] + c[i]);//比较是买票还是买IC卡便宜
    }
    printf("%lld\n", ans);
    return 0;
}

题解【洛谷P3406】海底高铁

原文：https://www.cnblogs.com/xsl19/p/12244193.html