Bỏ qua

DP động (Dynamic DP)

Kiến thức chuẩn bị: Ma trận, Phân rã chuỗi trên cây (HLD).

Quy hoạch động động (Dynamic DP) là một kỹ thuật nâng cao được giới thiệu bởi Mao Côn (猫锟) tại WC2018. Nó thường được sử dụng để giải quyết các bài toán DP trên cây có kèm theo các thao tác sửa đổi trọng số của đỉnh (hoặc cạnh).

Ví dụ

Lấy bài toán mẫu này làm ví dụ để giải thích quy trình của Dynamic DP.

Ví dụ Luogu P4719 【Mẫu】 Dynamic DP

Cho một cái cây có \(n\) đỉnh, mỗi đỉnh có một trọng số. Có \(m\) thao tác, mỗi thao tác cho \(x, y\) biểu thị việc sửa đổi trọng số của đỉnh \(x\) thành \(y\). Bạn cần tính kích thước trọng số của tập độc lập có trọng số lớn nhất trên cây sau mỗi thao tác.

Phép nhân ma trận mở rộng

Định nghĩa phép nhân ma trận mở rộng \(A \times B = C\) là:

\[ C_{i,j}=\max_{k=1}^{n}(A_{i,k}+B_{k,j}) \]

Điều này tương đương với việc thay phép nhân trong nhân ma trận thông thường bằng phép cộng, và phép cộng bằng phép \(\max\).

Đồng thời, phép nhân ma trận mở rộng này cũng thỏa mãn tính kết hợp, vì vậy có thể sử dụng lũy thừa ma trận nhanh.

Khi không có thao tác sửa đổi

Gọi \(f_{i,0}\) là đáp án lớn nhất khi không chọn đỉnh \(i\), \(f_{i,1}\) là đáp án lớn nhất khi chọn đỉnh \(i\).

Ta có phương trình DP:

\[ \begin{cases}f_{i,0}=\sum_{son}\max(f_{son,0},f_{son,1})\\f_{i,1}=w_i+\sum_{son}f_{son,0}\end{cases} \]

Đáp án sẽ là \(\max(f_{root,0}, f_{root,1})\).

Khi có thao tác sửa đổi

Đầu tiên, thực hiện phân rã chuỗi trên cây (HLD). Giả sử có một chuỗi nặng (heavy chain) như sau:

Gọi \(g_{i,0}\) là đáp án lớn nhất khi không chọn đỉnh \(i\) và chỉ cho phép chọn các đỉnh trong các cây con của các con nhẹ (light sons) của \(i\). Gọi \(g_{i,1}\) là đáp án lớn nhất khi chọn đỉnh \(i\) mà không tính đến con nặng \(son_i\). Ở đây \(son_i\) là con nặng của \(i\).

Giả sử chúng ta đã biết \(g_{i,0/1}\), ta có phương trình DP:

\[ \begin{cases}f_{i,0}=g_{i,0}+\max(f_{son_i,0},f_{son_i,1})\\f_{i,1}=g_{i,1}+f_{son_i,0}\end{cases} \]

Đáp án là \(\max(f_{root,0}, f_{root,1})\).

Ta có thể xây dựng ma trận:

\[ \begin{bmatrix} g_{i,0} & g_{i,0}\\ g_{i,1} & -\infty \end{bmatrix}\times \begin{bmatrix} f_{son_i,0}\\f_{son_i,1} \end{bmatrix}= \begin{bmatrix} f_{i,0}\\f_{i,1} \end{bmatrix} \]

Lưu ý rằng ở đây chúng ta sử dụng quy tắc nhân ma trận mở rộng.

Có thể thấy, khi thực hiện sửa đổi, ta chỉ cần cập nhật \(g_{i,1}\) và các chuỗi nặng hướng lên trên.

Ý tưởng cụ thể

  1. Dùng DFS tiền xử lý để tính \(f_{i,0/1}\) và \(g_{i,0/1}\).

  2. Thực hiện phân rã chuỗi trên cây (lưu ý: vì khi truy vấn một điểm ta cần tính tích ma trận trên đoạn từ điểm đó đến cuối chuỗi nặng chứa nó, nên với mỗi đỉnh cần ghi lại \(End_i\) là số hiệu của nút cuối cùng trong chuỗi nặng chứa \(i\)). Với mỗi chuỗi nặng, xây dựng một cây phân đoạn (Segment Tree) để duy trì ma trận \(g\) và tích các ma trận \(g\) trên đoạn.

  3. Khi sửa đổi: đầu tiên sửa đổi \(g_{i,1}\) và ma trận của nút \(i\) trong cây phân đoạn, tính toán sự thay đổi của ma trận tại \(top_i\) (đỉnh chuỗi nặng), sau đó cập nhật sự thay đổi này lên ma trận của cha của \(top_i\) (\(fa_{top_i}\)).

  4. Khi truy vấn: chỉ cần tính tích ma trận trên đoạn từ nút gốc (1) đến cuối chuỗi nặng chứa nó, cuối cùng lấy giá trị \(\max\) là xong.

Mã nguồn tham khảo 
  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

constexpr int MAXN = 500010;
constexpr int INF = 0x3f3f3f3f;

int Begin[MAXN], Next[MAXN], To[MAXN], e, n, m;
int sz[MAXN], son[MAXN], top[MAXN], fa[MAXN], dis[MAXN], p[MAXN], id[MAXN],
    End[MAXN];
// p[i]表示i树剖后的编号，id[p[i]] = i
int cnt, tot, a[MAXN], f[MAXN][2];

struct matrix {
  int g[2][2];

  matrix() { memset(g, 0, sizeof(g)); }

  matrix operator*(const matrix &b) const  // 重载矩阵乘
  {
    matrix c;
    for (int i = 0; i <= 1; i++)
      for (int j = 0; j <= 1; j++)
        for (int k = 0; k <= 1; k++)
          c.g[i][j] = max(c.g[i][j], g[i][k] + b.g[k][j]);
    return c;
  }
} Tree[MAXN], g[MAXN];  // Tree[]是建出来的线段树，g[]是维护的每个点的矩阵

void PushUp(int root) { Tree[root] = Tree[root << 1] * Tree[root << 1 | 1]; }

void Build(int root, int l, int r) {
  if (l == r) {
    Tree[root] = g[id[l]];
    return;
  }
  int Mid = (l + r) >> 1;
  Build(root << 1, l, Mid);
  Build(root << 1 | 1, Mid + 1, r);
  PushUp(root);
}

matrix Query(int root, int l, int r, int L, int R) {
  if (L <= l && r <= R) return Tree[root];
  int Mid = (l + r) >> 1;
  if (R <= Mid) return Query(root << 1, l, Mid, L, R);
  if (Mid < L) return Query(root << 1 | 1, Mid + 1, r, L, R);
  return Query(root << 1, l, Mid, L, R) *
         Query(root << 1 | 1, Mid + 1, r, L, R);
  // 注意查询操作的书写
}

void Modify(int root, int l, int r, int pos) {
  if (l == r) {
    Tree[root] = g[id[l]];
    return;
  }
  int Mid = (l + r) >> 1;
  if (pos <= Mid)
    Modify(root << 1, l, Mid, pos);
  else
    Modify(root << 1 | 1, Mid + 1, r, pos);
  PushUp(root);
}

void Update(int x, int val) {
  g[x].g[1][0] += val - a[x];
  a[x] = val;
  // 首先修改x的g矩阵
  while (x) {
    matrix last = Query(1, 1, n, p[top[x]], End[top[x]]);
    // 查询top[x]的原本g矩阵
    Modify(1, 1, n,
           p[x]);  // 进行修改(x点的g矩阵已经进行修改但线段树上的未进行修改)
    matrix now = Query(1, 1, n, p[top[x]], End[top[x]]);
    // 查询top[x]的新g矩阵
    x = fa[top[x]];
    g[x].g[0][0] +=
        max(now.g[0][0], now.g[1][0]) - max(last.g[0][0], last.g[1][0]);
    g[x].g[0][1] = g[x].g[0][0];
    g[x].g[1][0] += now.g[0][0] - last.g[0][0];
    // 根据变化量修改fa[top[x]]的g矩阵
  }
}

void add(int u, int v) {
  To[++e] = v;
  Next[e] = Begin[u];
  Begin[u] = e;
}

void DFS1(int u) {
  sz[u] = 1;
  int Max = 0;
  f[u][1] = a[u];
  for (int i = Begin[u]; i; i = Next[i]) {
    int v = To[i];
    if (v == fa[u]) continue;
    dis[v] = dis[u] + 1;
    fa[v] = u;
    DFS1(v);
    sz[u] += sz[v];
    if (sz[v] > Max) {
      Max = sz[v];
      son[u] = v;
    }
    f[u][1] += f[v][0];
    f[u][0] += max(f[v][0], f[v][1]);
    // DFS1过程中同时求出f[i][0/1]
  }
}

void DFS2(int u, int t) {
  top[u] = t;
  p[u] = ++cnt;
  id[cnt] = u;
  End[t] = cnt;
  g[u].g[1][0] = a[u];
  g[u].g[1][1] = -INF;
  if (!son[u]) return;
  DFS2(son[u], t);
  for (int i = Begin[u]; i; i = Next[i]) {
    int v = To[i];
    if (v == fa[u] || v == son[u]) continue;
    DFS2(v, v);
    g[u].g[0][0] += max(f[v][0], f[v][1]);
    g[u].g[1][0] += f[v][0];
    // g矩阵根据f[i][0/1]求出
  }
  g[u].g[0][1] = g[u].g[0][0];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  dis[1] = 1;
  DFS1(1);
  DFS2(1, 1);
  Build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int x, val;
    cin >> x >> val;
    Update(x, val);
    matrix ans = Query(1, 1, n, 1, End[1]);  // 查询1所在重链的矩阵乘
    cout << max(ans.g[0][0], ans.g[1][0]) << '\n';
  }
  return 0;
}

Bài tập tự luyện

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply