ABC369F Gather Coins

原题链接：F - Gather Coins

Tag：DP、Fenwick

题目描述

\(H \cdot W\)的网格上有 \(N\) 个硬币，第 \(i\) 个硬币在点 \((R_i,C_i)\) 上。找一条从 \((1,1)\) 到 \((H,W)\) 的路径（只能向下或向右走），使得路径上的硬币数最多。输出方案。

数据说明：

\(2\leq\ H,W\ \leq\ 2\times\ 10^5\)
\(1\leq\ N\ \leq\ \min(HW-2,\ 2\times\ 10^5)\)
\(1\leq\ R_i\ \leq\ H\)
\(1\leq\ C_i\ \leq\ W\)
\((R_i,C_i)\neq\ (1,1)\)
\((R_i,C_i)\neq\ (H,W)\)

分析

给定一个网格，只能向下或者向右走，这是一个十分经典的 \(\text{DP}\) 模型。

这道题首先可以想到一个十分朴素的 \(\text{DP}\) 方法，我们设计一个状态 \(dp_{i,j}\) 表示在 \((i,j)\) 处可以得到的最大硬币数量，那么就有如下转移：

\[\begin{gather*} dp_{i,j} = \max_{1 \leq u \leq i,1 \leq v \leq j}(dp_{u,v}) + a_{i,j} \end{gather*}\]

其中 \(a_{i,j}\) 表示 \((i,j)\) 这个点是否存在硬币。

但是这个解法显然是不可行的，因为这样根本开不下数组，更不必提时间复杂度是 \(O(HW)\) 的。

我们注意到上述的暴力转移，实质是一个二维偏序，这启示我们把点排序，之后就可以维护其中一维的最大答案，过程使用 \(\text{Fenwick}\) 实现。

由于问题最后要求输出路径方案，所以我们需要对于每一个点记录这个最大值是从哪里转移而来的，之后从终点向前构造路径方案即可。

在代码实现过程中，\(\text{Fenwick}\) 的单位是 \(pair<int,int>\)，其中 \(first\) 表示最大答案，\(second\) 表示从哪里转移而来，在更新 \(\text{Fenwick}\) 过程中只需要取 \(\max\) 就可以了。

代码实现

struct Fenwick {
    static const int fenwickMax = 2e5 + 5;
    int n; PII tree[fenwickMax];
    int lowBit(int x) { return -x & x; }
    void init(int x) { n = x; }
    void add(int x, PII k) {
        while (x <= n) {
            tree[x] = max(tree[x],k);
            x += lowBit(x);
        }
    }
    PII query(int x) {
        PII ans = {0,0};
        while (x) {
            ans = max(ans,tree[x]);
            x -= lowBit(x);
        }
        return ans;
    }
};
Fenwick fenwick;
void NeverSayNever() {
    int h, w, n;
    cin >> h >> w >> n;
    fenwick.init(w);
    vector<PII> vec(n + 2);
    vec[0] = {1,1};
    vec[n + 1] = {h, w};
    for (int i = 1; i <= n; ++i) {
        cin >> vec[i].first >> vec[i].second;
    }
    n++;
    vector<int> pre(n + 1);
    std::sort(vec.begin() + 1, vec.end());
    for (int i = 1; i <= n; ++i) {
        PII tmp = fenwick.query(vec[i].second);
        pre[i] = tmp.second;
        fenwick.add(vec[i].second, make_pair(tmp.first + 1, i));
    }
    cout << fenwick.query(w).first - 1 << endl;
    string ans;
    int tmp;
    for (int i = n; i; i = pre[i]) {
        tmp = pre[i];
        for (int j = vec[i].first - vec[tmp].first; j; --j) {
            ans.push_back('D');
        }
        for (int j = vec[i].second - vec[tmp].second; j; --j) {
            ans.push_back('R');
        }
    }
    std::reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

日志

本页面创建于 2024/09/23 21:45