题解 | #小美打怪 (图论解法)#

图论解法复杂度为 , 并不会比常规的 最长上升子序列做法 更优, 但是思路可以了解一下

已知, 若 h[i] > h[j] && a[i] > a[j], 那么节点 j 的答案一定至少为节点 i 的答案 +1, 用 dp 转移方程可以表示为 dp[j] = max(dp[j], dp[i]+1), 换句话说, 就是节点 j 的状态由其所有的前置节点确定

自然可以想到, 用一条有向边连接 i -> j, 表示 i 是 j 的 前置节点 , 因此对于一个节点 j, 可以用入度表示 前置节点 的数量, 当我们计算完所有 j 节点的 前置节点 的答案, j 节点的答案也就得到了, 这个过程与求图的 拓扑序 完全相同, 原问题就可以转化为类似于求图的直径的问题

不过还有一个问题, 这题的出发点是确定的, 假设为 0 节点 (即 H, A 代表的节点), 因此该题求的实际上是从 0 节点 出发, 最远可以在图中走多远

处理方法比较显然, 忽略所有 0 节点 不连接的点, 然后再求 拓扑序 即可 (因为 0 节点 不连接的点答案恒为 0, 可以认为不会为其指向的节点贡献答案, 因此可以去除这些节点的约束)

总结一下, 这个方法本质上是把原问题转换成了求图上路径的问题, 然后用 拓扑序 这个工具来求解, 也可以理解为一种对 dp 转移公式的图论解释

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int d = 0;
    vector<int> e;
};

int main() {
    int n, H, A;
    cin>>n>>H>>A;
    vector<int> h(n+1), a(n+1);
    h[0] = H;
    a[0] = A;
    for(int i = 1;i<=n;i++) {
        cin>>h[i];
    }
    for(int i = 1;i<=n;i++) {
        cin>>a[i];
    }

    vector<Node> nd(n+1);
    vector<bool> f(n+1);
    for(int i = 1;i<=n;i++) {
        if(h[0] > h[i] && a[0] > a[i]) {
            nd[0].e.push_back(i);
            nd[i].d++;
            f[i] = 1;
        }
    }

    for(int i = 1;i<=n;i++) {
        if(!f[i]) continue;
        for(int j = 1;j<=n;j++) {
            if(!f[j]) continue;
            if(i == j) continue;
            if(h[i] > h[j] && a[i] > a[j]) {
                nd[i].e.push_back(j);
                nd[j].d++;
            }
        }
    }

    queue<pair<int, int>> q;
    q.push({0, 0});

    int ans = 0;
    while(!q.empty()) {
        auto [cur, cnt] = q.front();
        q.pop();
        ans = max(ans, cnt);

        for(auto i:nd[cur].e) {
            nd[i].d--;
            if(nd[i].d == 0) q.push({i, cnt+1});
        }
    }

    cout<<ans;
}