动态DP

Posted on Edited on In Word count in article: 620 Reading time ≈ 2 mins.
动态动态规划, 那么就是信息是可以发生改变的Dp

DDp

大意

大概就是说, 有一棵树, 点权是会发生改变的, 让你动态求最大权独立集

分析

考虑到我们每次修改一个点, 能够受到影响的点就只有链上的点, 可以直接暴力更新

貌似这道题数据随机, 没有出到链的情况, 所以暴力更新是可以随便过的

先来一份暴力的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int n, m, p[maxn], f[maxn];
int dp[maxn][2], cur;
int head[maxn], edge[maxn << 1], __next[maxn << 1];

inline void AddEdge(int u, int v)
{
    __next[++cur] = head[u];
    head[u] = cur;
    edge[cur] = v;
}

inline void dfs(int u, int fa)
{
    dp[u][1] = p[u], dp[u][0] = 0;
    f[u] = fa;
    for (int i(head[u]); i; i = __next[i]) {
        if (edge[i] == fa) continue;
        dfs(edge[i], u);
        dp[u][0] += max(dp[edge[i]][0], dp[edge[i]][1]);
        dp[u][1] += dp[edge[i]][0];
    }
}

signed main()
{
    n = __read(), m = __read();
    for (int i = 1; i <= n; ++i) p[i] = __read();
    for (int i = 1; i < n; ++i) {
        int a = __read(), b = __read();
        AddEdge(a, b), AddEdge(b, a);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        int x = __read(), val = __read();
        int update = val - p[x];
        p[x] += update;
        int lst = x;
        int l0 = dp[x][0], l1 = dp[x][1];
        dp[x][1] += update;
        x = f[x];
        while (x) {
            int t0 = dp[x][0], t1 = dp[x][1];
            dp[x][0] -= max(l0, l1);
            dp[x][0] += max(dp[lst][0], dp[lst][1]);
            dp[x][1] += dp[lst][0] - l0;
            l0 = t0, l1 = t1;
            lst = x;
            x = f[x];
        }
        int ans = max(dp[1][1], dp[1][0]);
        printf ("%d\n", ans);
    }
    system("pause");
}//真挺暴力的

那么显然不能就这样说过去了的, 至少还是要看看别人这是怎么写的吧

正解

动态\(dp\)的套路是把\(dp\)方程写成矩阵乘法, 然后用什么\(LCT\), 树剖, 线段树, 倍增啥啥啥的维护一下

这道题的矩阵乘法大概是这个样子: \[ C_{i,j}=\max_{k=1}^n(A_{i,k}+B_{k,j}) \] 易证可以满足结合律, 可以像矩阵乘法一样乱写

然后就是构造矩阵, 找转移方程

老套路: \(f(i,0)\)表示这个点不作为独立集中的点, \(f(i,1)\)表示作为独立及中的点

那么显然有: \[ \begin{align*} f_{u,0}&=\sum _{v\in son_u}max(f_{v,0}, f_{v,1})\\ f_{u,1}&=val_u+\sum_{v\in sonu} f_{v,0} \end{align*} \]

啊，全局平衡二叉树还没会，先搁着

看看这？优质题解