\(\mathcal{Description}\)

Link.

给定你初始拥有的钱数 \(C\) 以及 \(N\) 台机器的属性，第 \(i\) 台有属性 \((d_i,p_i,r_i,g_i)\)，分别是出售时间、售价、转卖价、单日工作收益。机器在买入或转卖当天不提供收益，且你同一时刻最多拥有一台机器，在 \((D+1)\) 天时必须转卖拥有的机器。求第 \((D+1)\) 天你拥有的最大钱数。\(n\le10^5\)。

\(\mathcal{Solution}\)

比较自然的想法时依时间顺序 DP，所以先将机器按时间排序。令 \(f(i)\) 表示在 \(d_i\) 时刻，卖掉手里的机器后拥有的最大钱数，添加一台虚拟机器 \((D+1,0,0,0)\) 用于收集答案。考虑转移：

\[f(i)=\max_{f(j)\ge p_j}\{f(j)-p_j+r_j+g_j(d_i-d_j-1)\}.
\]

注意同一天多次买卖机器显然不优，所以 \(g_j\) 的系数不需要对 \(0\) 取 \(\max\)。这个一看就是斜优的样子，研究 \(f(u),f(v)\) 对 \(i\) 的转移：

\[\begin{aligned}
&f(u)-p_u+r_u+g_u(d_i-d_u-1)>f(v)-p_v+r_v+g_v(d_i-d_v-1) \\
\Longleftrightarrow~~~~&[f(u)-p_u+r_u-g_u(d_u+1)]-[f(v)-p_v-r_v-g_v(d_v+1)]>(g_v-g_u)d_i \\
\Longleftrightarrow~~~~&\frac{h(u)-h(v)}{g_u-g_v}<-d_i~~~~(g_u<g_v).
\end{aligned}
\]

很遗憾我们需要 \(g_u<g_v\) 控制符号，所以无法保证此时斜率 \(-d_i\) 的单调性，所以得写一发 CDQ 或者李超树。复杂度都是 \(\mathcal O(n\log n)\)。

\(\mathcal{Code}\)

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)

#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

typedef long long LL;

typedef long double LD;

inline void chkmax(LL& u, const LL v) { u < v && (u = v); }

const int MAXN = 1e5;

int N, C, D;

LL f[MAXN + 5], g[MAXN + 5];

struct Machine { int day, buy, sel, pro; } mch[MAXN + 5];

inline LD slope(const int u, const int v) {

    return LD(g[u] - g[v]) / (mch[u].pro - mch[v].pro);

}

inline std::vector<int> solve(const int l, const int r) {

    if (l == r) {

        chkmax(f[l], C);

        g[l] = f[l] - mch[l].buy + mch[l].sel

          - mch[l].pro * (mch[l].day + 1ll);

        // printf("f(%d)=%lld\n", l, f[l]);

        return f[l] >= mch[l].buy ? std::vector<int>{ l } : std::vector<int>{};

    }

    int mid = l + r >> 1;

    auto&& cvxL(solve(l, mid));

    for (int i = 0, j = mid + 1; j <= r; ++j) {

        while (i + 1 < int(cvxL.size())

          && slope(cvxL[i], cvxL[i + 1]) >= -mch[j].day) ++i;

        if (i < int(cvxL.size())) { // maybe cvxL is empty.

            int p = cvxL[i];

            chkmax(f[j], f[p] - mch[p].buy + mch[p].sel

              + mch[p].pro * (mch[j].day - mch[p].day - 1ll));

        }

    }

    auto&& cvxR(solve(mid + 1, r));

    std::vector<int> ret;

    auto push = [&](const int u) { // maintain the up-convex.

        while (ret.size() > 1 && slope(ret[ret.size() - 2], ret.back())

          <= slope(ret.back(), u)) ret.pop_back();

        ret.push_back(u);

    };

    for (size_t i = 0, j = 0; i < cvxL.size() || j < cvxR.size();) {

        if (i < cvxL.size() && j < cvxR.size()

          && mch[cvxL[i]].pro == mch[cvxR[j]].pro) {

            ++(g[cvxL[i]] < g[cvxR[j]] ? i : j); // pass the smaller one.

        } else if (j == cvxR.size()

          || (i < cvxL.size() && mch[cvxL[i]].pro < mch[cvxR[j]].pro)) {

            push(cvxL[i++]);

        } else {

            push(cvxR[j++]);

        }

    }

    return ret;

}

int main() {

    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

    while (std::cin >> N >> C >> D && N | C | D) {

        rep (i, 1, N) {

            std::cin >> mch[i].day >> mch[i].buy >> mch[i].sel >> mch[i].pro;

        }

        std::sort(mch + 1, mch + N + 1,

          [](const Machine& u, const Machine& v) { return u.day < v.day; });

        mch[++N] = { D + 1, 0, 0, 0 };

        rep (i, 1, N) f[i] = g[i] = 0;

        solve(1, N);

        static int cas = 0;

        std::cout << "Case " << ++cas << ": " << f[N] << '\n';

    }

    return 0;

}

巴特西

Solution -「WF2011」「BZOJ #3963」MachineWorks

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章