题解：P11593 [NordicOI 2024] Thin Ice

· · 题解

拿金币的后效性太大了，我们完全分析不出一个保证最优的贪心策略。如果你做过 [ARC098F] Donation 或者偶然注意到了样例分析中 Uolevi 不可能收集到大于 6 个金币，因为边缘所有格子的承受能力都小于等于 5 这句话，你就会想到倒推。

我们假设最后有 k 个金币，你从边上的一个格子出发，在满足重量限制的情况下可以随意走动，并可以在没有放过金币的格子放下一枚金币，如果 k 个金币都能放下就是合法。显然，遵从能放就放的贪心策略是不劣的。

你发现答案可以二分了。二分完 k 之后，如果你知道从哪个格子结束，那么通过用堆找可达的 d_{x, y} 最大的没放过金币的格子 (x, y)，内层可以 O(k \log k) 检验合法性。但是遗憾的是我们并不知道从哪个格子结束，如果全部枚举一遍就会超时。

此时我们需要知道，冰面上的移动并非无迹可寻，令相邻的两个格子 (x_1, y_1), (x_2, y_2) 之间有一条权值为 \min(d_{x_1, y_1}, d_{x_2, y_2}) 的边，那么原来点的重量限制就转化为边的重量限制。把最大生成树建出来，你发现只需要保留这些边就够了。

因此我们在二分内层对 kruskal 重构树进行 DP，设 f_p 表示 p 的子树可以随便走时，你最少剩下多少金币。初始条件是若 p 是叶子节点且对应原图的边界上的点，还要满足 k \leq d_{p_x, p_y}，那么 f_p = k - 1（当前位置就能先放下一个），否则 f_p = \infin。转移也简单，如果一个非叶子结点 p 满足 f_{ls_p} \leq lim_p（lim_p 是 p 对应的边的重量限制），那么 f_p = \min(f_p, f_{ls_p} - (siz_p - siz_{ls_p}))，意思是满足了 p 的重量限制，那么右子树自然可以随便走了。对右子树的转移同理。

如果 f_{root} \leq 0，说明可以放完，此时 k 合法。

DP 部分：

int lim[N * 2], f[N * 2], siz[N * 2], ls[N * 2], rs[N * 2];
inline void treedp(int pos, int x)
{
    if(is[pos] && x <= lim[pos]) f[pos] = x - 1;
    if(ls[pos] && rs[pos])
    {
        treedp(ls[pos], x), treedp(rs[pos], x);
        siz[pos] = siz[ls[pos]] + siz[rs[pos]];
        if(f[ls[pos]] <= lim[pos]) f[pos] = min(f[pos], f[ls[pos]] - (siz[pos] - siz[ls[pos]]));
        if(f[rs[pos]] <= lim[pos]) f[pos] = min(f[pos], f[rs[pos]] - (siz[pos] - siz[rs[pos]]));
    }
    else siz[pos] = 1;
}
inline bool check(int x)
{
    memset(f, 0x3f, sizeof(f));
    memset(siz, 0, sizeof(siz));
    treedp(dsu.idx, x);
    return (f[dsu.idx] <= 0);
}