Mashup Trainings Day 3: F0RE1GNERS' Contest 题解整合

ultmaster edited 6 年前

Problem A

wiki

Problem B

看似有零，其实没零。要打请打 kblack 。

UPD: 加强了数据，结果网上随便找的 std 好像挂了（难以置信）。现在数据可能是错的了。（妙啊）

方法一：类似这题的做法，加上减号以后更简单了，$(a, b)$ 转移到 $(3a+2b, b \cdot x)$，老方法线段树维护。

方法二：注意到因为加减号同时存在，一旦不是乘号，接下来所有的式子都有对偶可以抵消，于是转化成求前缀积乘常数的和，线段树维护，遇到 $0$ 的时候没有逆元可以做特殊记号处理。

Problem C

wiki

Problem D

Qingdao 2017.

根据题意模拟即可。请确保你的板子是对的。

Problem E

题意：有根树上有 $n$ 个节点，每个节点上有一个技能，每氪一点钱，技能就能升一级。如果掌握技能等级为 $x$，就可以获得 $x \cdot s_i$ 的收益。第 $i$ 个技能最高等级为 $h_i$。同时，如果要掌握技能 $i$，父亲节点上的技能至少要达到 $l_i$ 级。求在给定开销范围内，能得到的最大收益。

题解：这题官方题解是日文的。网上也没有相关的可阅读的材料。所以如果有错误欢迎指出。

考虑下述简化版问题：普通的 01 背包，物品之间存在一种树形的依赖关系（要取当前物品的话，父亲物品必须取）。这个问题的话，很容易想到一种树形 DP，记 f[u][w] 为 u 的子树，重量为 w 的最大收益。转移的时候要将若干子树合并。复杂度是 $\mathcal{O} (n w^2)$；计数问题的话，可以用 FFT 优化到 $\mathcal{O} (n w \log w)$，但意义并不大。但是：其实可以不合并子树的。假设节点 u 有孩子 a, b, c。可以这么考虑：

假如说我不管依赖关系，没选 u，直接把 a 的子树的 DP 按照普通的背包（非树形背包）做完了的话，我现在的背包结果要贡献到最终答案的话，u 是必选的。也就是说我把子树算完的结果，平移 u，加上 u 的收益就好了。
由于 a, b, c 子树之间是独立的，我更加可以用 f[a] 表示选完 a 后的结果，然后用 f[a] 去更新 f[b] 表示选完 b 后的结果……这跟最普通的 01 背包是一样的，只不过更新的过程改成了：递归去算一堆有关子树的东西。
所以思路就是，当到达 u 这个节点时，我假设 u 已经必选了，所以直接无视 u。然后先对现有的 u 从上面继承来的背包结果用 u 的所有子树去递归，递归结果就记在孩子身上。再用孩子的结果 + 必选 u 后的结果去更新 u 的背包就好了。
一定要想清楚到底在更新谁的背包，当前背包的意义是什么。

还是不理解的可以自行网搜「树形依赖背包」。网上的方法可能与这里介绍的方法在「更新顺序」上不大一样。

考虑原问题，原问题的难点在于：不同的子树对于 u 的个数的依赖是不同的，而且 u 可以选的个数可能比被依赖的要更多（也就是说，是多重背包问题）。

首先解决依赖个数不同的问题：在上一个问题的基础上，只要每次做完一棵子树都去更新一下「u 的背包」就好了。注意，依赖多的孩子被选择的时候，依赖少的孩子是肯定可以被选择的。所以按照孩子依赖的个数排个序，然后从小到大更新孩子。
u 可以选的个数比依赖的要多其实是一个更套路的问题：当前背包一旦确定，我就已经知道 u 必须要选几个了。剩下的那些部分可以随便挑。这是一个多重背包问题，可以用单调队列优化。不知道的可以自行网搜。

到此为止本问题已经全部解决，时间复杂度是 $\mathcal{O} (nk)$。常数较大，可能需要优化得比较好才能过。

核心代码如下：

vector<int> G[N];
int n; LL K;
LL h[N], s[N], p[N], l[N];
LL f[N][M], g[M];

void up(LL& a, const LL& b) { a = max(a, b); }

void backpack(LL *now, LL price, LL num, LL *ret) {
    deque<pair<LL, int> > q;
    FOR (i, 0, K + 1) {
        LL v = now[i] - i * price;
        while (!q.empty() && q.back().first <= v) q.pop_back();
        q.emplace_back(v, i);
        ret[i] = q.front().first + i * price;
        if (q.front().second == i - num) q.pop_front();
    }
}

void go(int u, LL* dp) {
    backpack(dp, s[u], h[u], f[u]);
    for (int &v: G[u]) {
        go(v, dp);
        dp = f[v];
        backpack(dp, s[u], h[u] - l[v], g);
        FOR (i, 0, K + 1 - l[v])
            up(f[u][i + l[v]], g[i] + s[u] * l[v]);
    }
}

int main() {
    FOR (i, 1, n + 1)
        sort(G[i].begin(), G[i].end(), [](int a, int b) { return l[a] < l[b]; });
    go(1, f[0]);
    cout << f[1][K] << endl;
}