[NOI2014]购票——斜率优化+树链剖分+线段树

建议到UOJ上去交

题解

一眼\(DP\)，先把转移方程写出来

设\(dp[i]\)为从点\(i\)出发到点\(1\)的最小费用，那么存在转移

\[f[i]=min\{f[j]+(d[i]-d[j])p[i]\}+q[i]=min\{f[j]-d[j]p[i]\}+d[i]*p[i]+q[i]
\]

这个式子看起来可以斜率优化啊，往下化几步，可以得到类似下面的东西：

若\(d[j] < d[k]\)，则当\(\frac{dp[j]-dp[k]}{d[j]-d[k]}\geqslant p[i]\)时从\(j\)转移更优，否则从\(k\)转移更优

这表明我们只需要维护一个下凸壳，转移时二分一下就行了

假设这个问题是在序列上且没有距离限制，你就已经可以\(O(nlogn)\)地\(A\)掉它了

加上距离限制时，我们可以拿个线段树维护一下每一小段的凸壳，查询时取个最大值

挪到树上时，只需要上个树剖

托上面两个东西的福，复杂度也变成了\(O(nlog^3n)\)[手动滑稽]

然后就是码码码

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200000

#define vi vector<int>

#define pb push_back

#define ll long long

#define INF 0x7f7f7f7f7f7f7f7f

#define LIM 17

int n, t;

vi G[MAXN + 5];

int summit[MAXN + 5], f[20][MAXN + 5], fa[MAXN + 5], top[MAXN + 5], sz[MAXN + 5], hson[MAXN + 5], id[MAXN + 5], dfn[MAXN + 5], dfn_clk;

ll d[MAXN + 5], s[MAXN + 5], p[MAXN + 5], q[MAXN + 5], l[MAXN + 5], dp[MAXN + 5];

namespace HLD {

    void dfs1(int u) {

        sz[u] = 1;

        f[0][u] = fa[u];

        for (int i = 1; i <= LIM; ++i) f[i][u] = f[i - 1][f[i - 1][u]];

        for (auto v : G[u]) {

            if (v == fa[u]) continue;

            d[v] = d[u] + s[v];

            dfs1(v);

            sz[u] += sz[v];

            if (sz[v] > sz[hson[u]]) hson[u] = v;

        }

    }

    void dfs2(int u, int tp) {

        top[u] = tp;

        dfn[u] = ++dfn_clk;

        id[dfn_clk] = u;

        if (hson[u]) dfs2(hson[u], tp);

        for (auto v : G[u]) {

            if (v == fa[u] || v == hson[u]) continue;

            dfs2(v, v);

        }

    }

}

double slope(int x, int y) {

    return static_cast<double>(dp[y] - dp[x])/(d[y] - d[x]);

}

void pre() {

    for (int i = 2; i <= n; ++i) {

        int u = i;

        for (int j = LIM; ~j; --j)

            if (d[i] - d[f[j][u]] <= l[i])

                u = f[j][u];

        summit[i] = !u ? 1 : u;

    }

}

namespace SegementTree {

    #define mid ((l + r) >> 1)

    #define lson (o << 1)

    #define rson (o << 1 | 1)

    vi ch[4 * MAXN + 5];

    void addPoint(vi &v, int x) { // 把点x扔进下凸壳

        while (v.size() >= 2 && slope(x, v[v.size() - 2]) < slope(v[v.size() - 1], v[v.size() - 2])) v.pop_back();

        v.push_back(x);

    }

    ll get(vi &v, ll p) { // 在凸壳上二分斜率

        if (v.size() == 1) return dp[v[0]] - d[v[0]] * p;

        ll ret = INF;

        int l = 0, r = v.size() - 1, m;

        double s1, s2;

        while (l <= r) {

            m = (l + r) >> 1;

            if (m == v.size() - 1) {

                s1 = slope(v[m - 1], v[m]);

                ret = min(ret, dp[v[m]] - d[v[m]] * p);

                if (s1 <= p) l = m + 1;

                else r = m - 1;

            }

            else if (!m) {

                s2 = slope(v[m], v[m + 1]);

                ret = min(ret, dp[v[m]] - d[v[m]] * p);

                if (s2 <= p) l = m + 1;

                else r = m - 1;

            }

            else {

                s1 = slope(v[m - 1], v[m]);

                s2 = slope(v[m], v[m + 1]);

                ret = min(ret, dp[v[m]] - d[v[m]] * p);

                if (s1 <= p && s2 <= p) l = m + 1;

                else if(s1 <= p && s2 > p) return min(ret, dp[v[m]] - d[v[m]] * p);

                else r = m - 1;

            }

        }

        return ret;

    }

    void insert(int o, int l, int r, int x, int u) { // 插入一个点

        addPoint(ch[o], u);

        if (l == r) return ;

        if (x <= mid) insert(lson, l, mid, x, u);

        else insert(rson, mid + 1, r, x, u);

    }

    ll query(int o, int l, int r, int L, int R, ll p) { // 在那一堆凸壳中找最小值

        if (L <= l && r <= R) return get(ch[o], p);

        ll ret = INF;

        if (L <= mid) ret = min(ret, query(lson, l, mid, L, R, p));

        if (R > mid) ret = min(ret, query(rson, mid + 1, r, L, R, p));

        return ret;

    }

    #undef mid

    #undef lson

    #undef rson

}

using namespace SegementTree;

void update(int u) { // 求点u的DP值

    dp[u] = INF;

    int x = fa[u];

    while (d[top[x]] >= d[summit[u]]) {

        dp[u] = min(dp[u], query(1, 1, n, dfn[top[x]], dfn[x], p[u]) + d[u] * p[u] + q[u]);

        x = fa[top[x]];

    }

    if (d[x] >= d[summit[u]]) dp[u] = min(dp[u], query(1, 1, n, dfn[summit[u]], dfn[x], p[u]) + d[u] * p[u] + q[u]);

}

void work(int u) {

    if (u != 1) update(u);

    insert(1, 1, n, dfn[u], u);

    for (auto v : G[u]) {

        if (v == fa[u]) continue;

        work(v);

    }

}

int main() {

    scanf("%d%d", &n, &t);

    for (int i = 2; i <= n; ++i) {

        scanf("%d%lld%lld%lld%lld", &fa[i], &s[i], &p[i], &q[i], &l[i]);

        G[fa[i]].pb(i);

    }

    HLD::dfs1(1);

    HLD::dfs2(1, 1);

    d[0] = -1;

    pre();

    work(1);

    for (int i = 2; i <= n; ++i) printf("%lld\n", dp[i]);

    return 0;

}

巴特西

[NOI2014]购票——斜率优化+树链剖分+线段树

题解

最新文章

热门文章