动态 DP 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-03-18 22:54

点击数:137

动态 DP 在 NOIP2018D2T3 考察后风靡 OI 圈,然而我却一直没学。

引入

考虑这样一个问题:

给定一棵 $n$ 个点的树,点有点权 $w_i$。
有 $m$ 次操作,每次操作给定 $x,y$,表示将 $w_x$ 修改为 $y$。
每次操作后,询问这棵树的最大权独立集的权值大小。
$n,m \le 10^5$。

如果只有一次询问,我们显然可以用这样一个简单地树形 dp 解决:

设根为 $rt$。

设 $f_{i,0/1}$ 表示 $i$ 点不选/选时,$i$ 的子树内的最大答案。

转移为:

$$
\begin{cases}f_{x,0} = \sum_{y \in son_x} \max(f_{y,0}, f_{y,1}) \\f_{x,1} = w_x + \sum_{y \in son_x} f_{y,0}\end{cases}
$$

目标为 $\max(f_{rt,0}, f_{rt,1})$。

多次询问呢?

这时候就需要可以解决树上带修 DP 问题的算法,也就是动态 DP

动态 DP

广义矩阵乘法

定义广义矩阵乘法 $A \times B = C$ 为:
$$
C_{i,j} = \max_{k=1}^{n}(A_{i,k} + B_{k,j})
$$
即,将普通矩阵乘法中的乘法变成加法,加法变成取 $\max$。

同时,广义矩阵乘法满足结合律,所以可以使用矩阵快速幂。

动态 DP

首先进行树链剖分,设 $h_i$ 表示 $i$ 的重儿子。

设 $g_{i,0/1}$ 表示不选择/选择 $i$,同时只选择 $i$ 的轻儿子所在的子树的最大答案。

则有转移:
$$
\begin{cases}g_{x,0} = \sum_{y \in son_x, y \ne h_i} \max(f_{y,0}, f_{y,1}) \\g_{x,1} = w_x + \sum_{y \in son_x, y \ne h_i} f_{y,0} \\f_{x,0} = g_{x,0} + \max(f_{h_x, 0}, f_{h_x, 1}) \\f_{x,1} = g_{x,1} + f_{h_x,0}\end{cases}
$$
目标同样为 $\max(f_{rt,0}, f_{rt,1})$。

注意,这个转移是先计算 $g$ 后计算 $f$ 的,因此我们需要先处理轻儿子,然后处理重儿子。

考虑用线段树维护每条链的 dp 值,这样我们就可以单次 $\mathcal O(\log^2 n)$ 修改并回答询问了。

如何维护呢?

观察 $f$ 的转移,可以发现它等价于广义矩阵乘法的转移形式:
$$
\begin{bmatrix}g_{i,0} & g_{i,0}\\g_{i,1} & -\infty\end{bmatrix}\times \begin{bmatrix}f_{h_i,0} & 0\\f_{h_i,1} & 0\end{bmatrix}=\begin{bmatrix}f_{i,0} & 0\\f_{i,1}& 0\end{bmatrix}
$$

因此,对于每个点,我们维护矩阵 $\begin{bmatrix}g_{i,0} & g_{i,0}\\g_{i,1} & -\infty\end{bmatrix}$,则一条链的链顶的 $\begin{bmatrix}f_{i,0} & 0\\f_{i,1}& 0\end{bmatrix}$,就等于这条链上的矩阵从上到下相乘后的矩阵。

于是,我们用线段树维护矩阵 $\begin{bmatrix}g_{i,0} & g_{i,0}\\g_{i,1} & -\infty\end{bmatrix}$ 的连乘积就可以了。

【模板】P4719 【模板】动态 DP

const int N = 1e5 + 7, inf = 1e9;
int n, m, w[N], d[N], f[N], s[N], son[N];
int dfn[N], rnk[N], top[N], pot[N], num, F[N][2], G[N][2];
vi e[N];
struct mat {
    int a[2][2];
    inline mat() { memset(a, 0, sizeof(a)); }
    inline friend mat operator * (mat a, mat b) {
        mat c;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    c.a[i][j] = max(c.a[i][j], a.a[i][k] + b.a[k][j]);
        return c;
    }
} g[N];
struct T {
    int l, r;
    mat a;
} t[N<<2];

void dfs(int x) {
    s[x] = 1, F[x][1] = w[x];
    for (int y : e[x])
        if (y != f[x]) {
            f[y] = x, d[y] = d[x] + 1;
            dfs(y), s[x] += s[y];
            if (s[y] > s[son[x]]) son[x] = y;
            F[x][0] += max(F[y][0], F[y][1]);
            F[x][1] += F[y][0];
        }
}

void dfs(int x, int p) {
    dfn[x] = ++num, rnk[num] = x;
    top[x] = p, pot[p] = x;
    G[x][1] = w[x];
    if (son[x]) dfs(son[x], p);
    for (int y : e[x])
        if (y != f[x] && y != son[x]) {
            dfs(y, y);
            G[x][0] += max(F[y][0], F[y][1]);
            G[x][1] += F[y][0];
        }
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) return t[p].a = g[rnk[l]], void();
    build(ls, l, md), build(rs, md + 1, r);
    t[p].a = t[ls].a * t[rs].a;
}

void mdf(int p, int x) {
    if (t[p].l == t[p].r) return t[p].a = g[rnk[x]], void();
    mdf(x <= md ? ls : rs, x);
    t[p].a = t[ls].a * t[rs].a;
}

mat ask(int p, int l, int r) {
    if (t[p].l >= l && t[p].r <= r) return t[p].a;
    if (r <= md) return ask(ls, l, r);
    if (l > md) return ask(rs, l, r);
    return ask(ls, l, r) * ask(rs, l, r);
}

inline void change(int x, int y) {
    g[x].a[1][0] += y - w[x], w[x] = y;
    while (x) {
        mat lst = ask(1, dfn[top[x]], dfn[pot[top[x]]]);
        mdf(1, dfn[x]);
        mat now = ask(1, dfn[top[x]], dfn[pot[top[x]]]);
        x = f[top[x]];
        int o = max(now.a[0][0], now.a[1][0]) - max(lst.a[0][0], lst.a[1][0]);
        g[x].a[0][0] = g[x].a[0][1] += o;
        g[x].a[1][0] += now.a[0][0] - lst.a[0][0];
    }
}

int main() {
    rd(n), rd(m), rda(w, n);
    for (int i = 1, x, y; i < n; i++)
        rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    for (int i = 1; i <= n; i++)
        reverse(e[i].begin(), e[i].end()); 
    d[1] = 1, dfs(1), dfs(1, 1);
    for (int i = 1; i <= n; i++)
        g[i].a[0][0] = g[i].a[0][1] = G[i][0],
        g[i].a[1][0] = G[i][1], g[i].a[1][1] = -inf;
    build(1, 1, n);
    for (int i = 1, x, y; i <= m; i++) {
        rd(x), rd(y), change(x, y);
        mat ans = ask(1, 1, dfn[pot[1]]);
        print(max(ans.a[0][0], ans.a[1][0]));
    }
    return 0;
}

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注