Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P7480 Reboot from Blue

发表于 分类于
本文字数： 3.8k 阅读时长 ≈ 3 分钟
标签：            

P7480 Reboot from Blue

首先发现一个性质，换油一定是从价格更贵的换为价格更低的。

Algorithm I DP

对所有的加油站按照价格从大到小排序，$f _ i$ 表示从起点到 $i$ 点的最小代价。可以得到
$$
f _ i = \min _ {j < i}\{ f _ j + c _ j \left | x _ i - x _ j \right | \}
$$
直接计算，复杂度为 $O(n ^2)$ ，可以得到 $40pts$ 。

查看代码 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL st, ed, f[N];
struct Node
{
    LL x, c;
    void input()
    {
        scanf("%lld%lld", &c, &x);
    }
    bool operator<(const Node &_) const
    {
        return c > _.c;
    }
} w[N];
int main()
{
    scanf("%d%lld%lld", &n, &st, &ed);
    for (int i = 1; i <= n; i++)
        w[i].input();
    sort(w + 1, w + n + 1);
    int t;
    for (int i = 1; i <= n; i++)
        if (st == w[i].x)
            t = i;
    for (int i = 1; i <= n; i++)
        f[i] = abs(w[i].x - w[t].x) * w[t].c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            f[i] = min(f[i], f[j] + abs(w[i].x - w[j].x) * w[j].c);
    LL res = abs(w[t].x - ed) * w[t].c;
    for (int i = 1; i <= n; i++)
        res = min(res, f[i] + abs(w[i].x - ed) * w[i].c);
    printf("%lld", res);
    return 0;
}

Algorithm II Shortest Path

显然，一个点只会转移到左右第一个比它价格小的点，单调栈建图，跑最短路。特别的，终点可以视为一个价格为 $0$ 的点。

查看代码 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const LL inf = 3e18;
const int N = 1e5 + 10, M = 2e5 + 10;
bool vis[N];
int top, stk[N];
int n, st, ed;
LL wt[M], d[N];
int idx, hd[N], nxt[M], edg[M];
struct Node
{
    LL c, x;
    void input()
    {
        scanf("%lld%lld", &c, &x);
    }
    bool operator<(const Node &_) const
    {
        return x < _.x || (x == _.x && c < _.c);
    }
} w[N];
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = abs(w[a].x - w[b].x) * w[a].c;
}
int main()
{
    int s, t;
    scanf("%d%d%d", &n, &s, &t);
    for (int i = 1; i <= n; i++)
        w[i].input();
    w[++n] = (Node){0, t};
    sort(w + 1, w + n + 1);
    for (int i = 1; i <= n; i++)
        if (w[i].x == s)
        {
            st = i;
            break;
        }
    for (int i = 1; i <= n; i++)
        if (!w[i].c)
        {
            ed = i;
            break;
        }
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1; i <= n; i++)
    {
        while (top && w[stk[top]].c > w[i].c)
        {
            add(stk[top], i);
            top--;
        }
        stk[++top] = i;
    }
    top = 0;
    for (int i = n; i; i--)
    {
        while (top && w[stk[top]].c > w[i].c)
        {
            add(stk[top], i);
            top--;
        }
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++)
        d[i] = inf;
    d[st] = 0;
    queue<int> q;
    q.push(st);
    vis[st] = true;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (d[t] + wt[i] < d[edg[i]])
            {
                d[edg[i]] = d[t] + wt[i];
                if (!vis[edg[i]])
                {
                    vis[edg[i]] = true;
                    q.push(edg[i]);
                }
            }
    }
    printf("%lld", d[ed]);
    return 0;
}
相关文章