題目
題目鏈接
解題思路
首先油價是大于0的，油箱是無限的，因此我們不會從油價低的地方到油價高的地方去加油，我們可以根據每個地方油價的從高到低依次更新，
考慮某次到達點t后，其油價是v，那么對另一點s的貢獻是v*abs(t-s)，這是兩條直線，
考慮到我們是動態的確定點，并添加直線，因此維護下凸殼即可，
使用線段添加的李超樹，復雜度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)，
代碼
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define lson rt * 2
#define rson rt * 2 + 1
typedef long long ll;
const int N = 1e5 + 100;
int n, s, t, tp, cnt;
int has[N], val[N];
ll dp[N];
struct Line {
ll k, b;
Line() { k = 0; b = 1e18; }
Line(ll k, ll b) :k(k), b(b) {}
ll cal(ll x) {
return k * x + b;
}
}tree[N * 4];
void insert(Line x, int l, int r, int rt) {
int m = (l + r) / 2;
if (tree[rt].cal(has[m]) > x.cal(has[m])) swap(tree[rt], x);
if (l == r) return;
if (tree[rt].cal(has[l]) > x.cal(has[l])) insert(x, l, m, lson);
else insert(x, m + 1, r, rson);
}
void insert(int rl, int rr, Line x, int l, int r, int rt) {
if (rl == l && rr == r) return void(insert(x, l, r, rt));
int m = (l + r) / 2;
if (rr <= m) insert(rl, rr, x, l, m, lson);
else if (m < rl) insert(rl, rr, x, m + 1, r, rson);
else {
insert(rl, m, x, l, m, lson);
insert(m + 1, rr, x, m + 1, r, rson);
}
}
void query(int id, Line &res, int l, int r, int rt) {
if (tree[rt].cal(has[id]) < res.cal(has[id])) res = tree[rt];
if (l == r) return;
int m = (l + r) / 2;
if (id <= m) query(id, res, l, m, lson);
else query(id, res, m + 1, r, rson);
}
struct node {
int w, id;
}sa[N];
bool operator < (node a, node b) {
return a.w > b.w;
}
int get(int id) {
return lower_bound(has + 1, has + tp + 1, id) - has;
}
int main() {
//freopen("0.txt", "r", stdin);
scanf("%d%d%d", &n, &s, &t);
for (int i = 1; i <= n; i++) scanf("%d%d", &sa[i].w, &sa[i].id), has[++tp] = sa[i].id;
has[++tp] = s; has[++tp] = t;
sort(has + 1, has + tp + 1);
tp = unique(has + 1, has + tp + 1) - has - 1;
memset(val, 0x3f3f3f3f, sizeof(val));
s = get(s); t = get(t);
for (int i = 1; i <= n; i++) {
sa[i].id = get(sa[i].id);
val[sa[i].id] = min(val[sa[i].id], sa[i].w);
if (sa[i].id == s) sa[i].w = 0;
}
sort(sa + 1, sa + n + 1);
insert(s, tp, Line(val[s], -1LL * has[s] * val[s]), 1, tp, 1);
insert(1, s, Line(-val[s], 1LL * has[s] * val[s]), 1, tp, 1);
for (int i = 1; sa[i].w; i++) {
if (sa[i].w != val[sa[i].id]) continue;
Line res; int id = sa[i].id;
query(id, res, 1, tp, 1);
dp[id] = res.cal(has[id]);
insert(1, id, Line(-val[id], dp[id] + 1LL * has[id] * val[id]), 1, tp, 1);
insert(id, tp, Line(val[id], dp[id] - 1LL * has[id] * val[id]), 1, tp, 1);
}
Line res;
query(t, res, 1, tp, 1);
printf("%lld\n", res.cal(has[t]));
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273356.html
標籤：其他
上一篇：求生存系列：序言
下一篇：raspberry pi pico|爺青回！在raspberry pi pico上玩nes游戲(1)(開源pico NES模擬器)-效果演示及介紹