动态DP

程序员文章站 2022-07-12 09:19:54

...

动态DP

最大权独立集

修改树上的点权, 并查询最大权独立集, 即选出一些不相邻的点, 使他们点权和最大

点数和操作数\(n, m(\le 10^5)\)

假如不修改的话:

设\(f[x][0/1]\)表示这个点选不选时, 整棵子树的最大点权和
\(f[u][0]=\sum \max(f[v][0/1])\)
\(f[u][1]=\sum f[v][0]+Val(u)\)

那么要修改查询怎么办呢?

熟练剖分
套路是利用矩阵表示\(DP\)方程, 然后利用矩阵的结合律和线段树的区间维护, 来快速修改查询区间的值
设\(f[x]\)为这个点的真答案, \(g[x]\)为这个点除了重子树外的假答案
- 这样每次修改就只需要更新到根的路径中,轻儿子连到的那个重链的点的\(g\)值即可

以这道题具体来说:

设\(g[u][0/1]\)表示这个点除了重子树外取与不取的最大权值和

将矩阵\(C[i][j]=\sum A[i][k]*B[k][j]\)改为\(C[i][j]=\max(A[i][k]+B[k][j])\)

至于为什么魔改之后仍满足结合律,参考floyd的代码实现就可以了

三个for枚举并取\(\max\),显然两次矩乘先后乘都没关系

继续:
\[ \begin{bmatrix} g[u][0] & g[u][0] \\ g[u][1] & -\infty \\ \end{bmatrix} * \begin{bmatrix} f[hson][0] \\ f[hson][1] \end{bmatrix} = \begin{bmatrix} f[u][0] \\ f[u][1] \end{bmatrix} \]
那么在一条重链上:
\[ \prod_{i=1}^{n-1} \begin{bmatrix} g[i][0] & g[i][0] \\ g[i][1] & -\infty \\ \end{bmatrix} * \begin{bmatrix} f[n][0] \\ f[n][1] \end{bmatrix} = \begin{bmatrix} f[1][0] \\ f[1][1] \end{bmatrix} \]
由于在记录一个\(f\)矩阵太烦了, 思考怎么用\(g\)表示\(f\)

由于\(g[n][0/1]=f[n][0/1]\)
\[ \begin{bmatrix} g[n][0] & g[n][0] \\ g[n][1] & -\infty \\ \end{bmatrix} * \begin{bmatrix} 0 \\ -\infty \\ \end{bmatrix} = \begin{bmatrix} f[n][0] \\ f[n][1] \\ \end{bmatrix} \]
于是变成
\[ \prod_{i=1}^{n} \begin{bmatrix} g[i][0] & g[i][0] \\ g[i][1] & -\infty \\ \end{bmatrix} * \begin{bmatrix} 0 \\ -\infty \end{bmatrix} = \begin{bmatrix} f[1][0] \\ f[1][1] \end{bmatrix} \]
那么显然可以用线段树维护左边那个矩阵连乘, 支持单点修改, 根的值查询即可

查询完答案后乘上那个转移用的矩阵就完事了

总结一下:

对于修改一个点\(x\)的权值, 他只影响他到根的路径上的点:

根据\(g\)函数的性质, 重新修改它
修改这个点到这条重链顶端的区间
记录修改前后的链顶的值, 用于更新链顶父亲的\(g\)
跳到链顶的父亲, 循环直到根

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 10;
const LL INF = 1e14;

inline LL in()
{
    LL x = 0, flag = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * flag;
}

int n, m;
LL a[MAXN], f[MAXN][2], g[MAXN][2];

int nume, head[MAXN];
struct Adj { int nex, to; } adj[MAXN << 1];
void addedge(int from, int to)
{
    adj[++ nume] = (Adj) { head[from], to };
    head[from] = nume;
}
struct Matrix
{
    LL val[2][2];
    Matrix () { memset(val, 0, sizeof val); }
    Matrix (LL a, LL b, LL c, LL d) { val[0][0] = a, val[0][1] = b, val[1][0] = c, val[1][1] = d;}
    Matrix (int x) { val[0][0] = val[0][1] = g[x][0], val[1][0] = g[x][1], val[1][1] = -INF; }
    Matrix operator * (const Matrix B)
        {
            Matrix C;
            for (int i = 0; i < 2; ++ i)
                for (int j = 0; j < 2; ++ j)
                    for (int k = 0; k < 2; ++ k)
                        C.val[i][j] = max(C.val[i][j], val[i][k] + B.val[k][j]);
            return C;
        }
    void print() { printf("%lld %lld\n%lld %lld\n", val[0][0], val[0][1], val[1][0], val[1][1]); }
} I;

int fa[MAXN], siz[MAXN], hson[MAXN];
void DFS1(int u) // fa, siz, hson
{
    siz[u] = 1;
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        DFS1(v);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]]) hson[u] = v;
    }
}
int ind, id[MAXN], aid[MAXN], top[MAXN], btm[MAXN];
void DFS2(int u, int t) // id, aid, top, btm
{
    aid[id[u] = ++ ind] = u; top[u] = t;
    if (hson[u]) DFS2(hson[u], t), btm[u] = btm[hson[u]];
    else btm[u] = u;
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa[u] || v == hson[u]) continue;
        DFS2(v, v);
    }
}

#define ls (now << 1)
#define rs (now << 1 | 1)
#define mid ((l + r) >> 1)
Matrix t[MAXN << 2];
void build(int now, int l, int r)
{
    if (l == r) return (void) (t[now] = Matrix(aid[l]));
    build(ls, l, mid); build(rs, mid + 1, r);
    t[now] = t[ls] * t[rs];
}
void modify(int now, int l, int r, int x)
{
    if (x < l || r < x) return;
    if (l == r) return (void) (t[now] = Matrix(aid[x]));
    modify(ls, l, mid, x); modify(rs, mid + 1, r, x);
    t[now] = t[ls] * t[rs];
}
Matrix query(int now, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return t[now];
    if (y <= mid) return query(ls, l, mid, x, y);
    else if (x >= mid + 1) return query(rs, mid + 1, r, x, y);
    else return query(ls, l, mid, x, y) * query(rs, mid + 1, r, x, y);
}
#undef ls
#undef rs
#undef mid

void init(int u) // f[0] = sum(max(f[v0], f[v1])), f[1] = a[u] + sum(f[v0])
{
    g[u][1] = f[u][1] = a[u];
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa[u]) continue;
        init(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
        if (v != hson[u])
            {
                g[u][0] += max(f[v][0], f[v][1]);
                g[u][1] += f[v][0];
            }
    }
}
void uppath(int x, LL y)
{
    g[x][1] += y;
    Matrix now; LL pre0, pre1;
    while (x)
    {
        pre0 = f[top[x]][0], pre1 = f[top[x]][1];
        modify(1, 1, n, id[x]);
        now = query(1, 1, n, id[top[x]], id[btm[x]]) * I;
        f[top[x]][0] = now.val[0][0];
        f[top[x]][1] = now.val[1][0];
        x = fa[top[x]];
        g[x][1] += now.val[0][0] - pre0;
        g[x][0] += max(now.val[0][0], now.val[1][0]) - max(pre0, pre1);
    }
}

int main()
{
    I = Matrix(0, -INF, -INF, 0); 
    n = in(), m = in();
    for (int i = 1; i <= n; ++ i) a[i] = in();
    for (int i = 1; i < n; ++ i)
    {
        int x = in(), y = in();
        addedge(x, y); addedge(y, x);
    }
    DFS1(1); DFS2(1, 1);
    init(1); build(1, 1, n);
    Matrix ret;
    while (m --)
    {
        LL x = in(), y = in();
        uppath(x, y - a[x]); a[x] = y;
        ret = query(1, 1, n, id[top[1]], id[btm[1]]) * I;
        printf("%lld\n", max(ret.val[0][0], ret.val[1][0]));
    }
    return 0;
}
/*201907191515~1809 */

NOIp2019 D2T3 保卫王国

同样

定义矩阵乘法\(C[i][j]=\max(A[i][k]+B[k][j])\)
\[ \begin{bmatrix} \infty & g[u][0] \\ g[u][1] & g[u][1] \\ \end{bmatrix} * \begin{bmatrix} f[hson][0] \\ f[hson][1] \end{bmatrix} = \begin{bmatrix} f[u][0] \\ f[u][1] \end{bmatrix} \]

\[ \begin{bmatrix} \infty & g[u][0] \\ g[u][1] & g[u][1] \\ \end{bmatrix} * \begin{bmatrix} 0 & \infty\\ \infty & 0\\ \end{bmatrix} = \begin{bmatrix} 不关键 & f[n][0] \\ 不关键 & f[n][1] \\ \end{bmatrix} \]

\[ ans= \prod_{i=1}^{n} \begin{bmatrix} \infty & g[u][0] \\ g[u][1] & g[u][1] \\ \end{bmatrix} * \begin{bmatrix} 0 & \infty\\ \infty & 0\\ \end{bmatrix} = \begin{bmatrix} 不关键 & f[1][0] \\ 不关键 & f[1][1] \\ \end{bmatrix} \]

那么如果一个点必须选, 就给他的值减去\(\infty\),必须不选同理

假如两个点都必须不选,而算出来的答案\(>\infty\), 说明他们两个有连边, 所以算法只能至少选择其中一个, 输出\(-1\)即可

然后再修改回去

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 10;
const LL INF = 1e14;

inline LL in()
{
    LL x = 0, flag = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * flag;
}

int n, m;
LL a[MAXN], f[MAXN][2], g[MAXN][2];

int nume, head[MAXN];
struct Adj { int nex, to; } adj[MAXN << 1];
void addedge(int from, int to)
{
    adj[++ nume] = (Adj) { head[from], to };
    head[from] = nume;
}
struct Matrix
{
    LL val[2][2];
    Matrix () { memset(val, 0x3f3f3f, sizeof val); }
    Matrix (LL a, LL b, LL c, LL d) { val[0][0] = a, val[0][1] = b, val[1][0] = c, val[1][1] = d;}
    Matrix (int x) { val[0][0] = INF, val[0][1] = g[x][0], val[1][0] = val[1][1] = g[x][1]; }
    Matrix operator * (const Matrix B)
        {
            Matrix C;
            for (int i = 0; i < 2; ++ i)
                for (int j = 0; j < 2; ++ j)
                    for (int k = 0; k < 2; ++ k)
                        C.val[i][j] = min(C.val[i][j], val[i][k] + B.val[k][j]);
            return C;
        }
    void print() { printf("%lld %lld\n%lld %lld\n", val[0][0], val[0][1], val[1][0], val[1][1]); }
} I;

int fa[MAXN], siz[MAXN], hson[MAXN];
void DFS1(int u) // fa, siz, hson
{
    siz[u] = 1;
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        DFS1(v);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]]) hson[u] = v;
    }
}
int ind, id[MAXN], aid[MAXN], top[MAXN], btm[MAXN];
void DFS2(int u, int t) // id, aid, top, btm
{
    aid[id[u] = ++ ind] = u; top[u] = t;
    if (hson[u]) DFS2(hson[u], t), btm[u] = btm[hson[u]];
    else btm[u] = u;
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa[u] || v == hson[u]) continue;
        DFS2(v, v);
    }
}

#define ls (now << 1)
#define rs (now << 1 | 1)
#define mid ((l + r) >> 1)
Matrix t[MAXN << 2];
void build(int now, int l, int r)
{
    if (l == r) return (void) (t[now] = Matrix(aid[l]));
    build(ls, l, mid); build(rs, mid + 1, r);
    t[now] = t[ls] * t[rs];
}
void modify(int now, int l, int r, int x)
{
    if (x < l || r < x) return;
    if (l == r) return (void) (t[now] = Matrix(aid[x]));
    modify(ls, l, mid, x); modify(rs, mid + 1, r, x);
    t[now] = t[ls] * t[rs];
}
Matrix query(int now, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return t[now];
    if (y <= mid) return query(ls, l, mid, x, y);
    else if (x >= mid + 1) return query(rs, mid + 1, r, x, y);
    else return query(ls, l, mid, x, y) * query(rs, mid + 1, r, x, y);
}
#undef ls
#undef rs
#undef mid

void init(int u) // f[1] = sum(min(f[v0], f[v1])) + a[u], f[0] = sum(f[v1])
{
    g[u][1] = f[u][1] = a[u];
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa[u]) continue;
        init(v);
        f[u][1] += min(f[v][0], f[v][1]);
        f[u][0] += f[v][1];
        if (v != hson[u])
            {
                g[u][1] += min(f[v][0], f[v][1]);
                g[u][0] += f[v][1];
            }
    }
}
void uppath(int x, LL y)
{
    g[x][1] += y;
    Matrix now; LL pre0, pre1;
    while (x)
    {
        pre0 = f[top[x]][0], pre1 = f[top[x]][1];
        modify(1, 1, n, id[x]);
        now = query(1, 1, n, id[top[x]], id[btm[x]]) * I;
        f[top[x]][0] = now.val[0][1];
        f[top[x]][1] = now.val[1][1];
        x = fa[top[x]];
        g[x][0] += now.val[1][1] - pre1;
        g[x][1] += min(now.val[0][1], now.val[1][1]) - min(pre0, pre1);
    }
}
char fuck[5];
int main()
{
    I = Matrix(0, INF, INF, 0); 
    n = in(), m = in(); scanf("%s", fuck);
    for (int i = 1; i <= n; ++ i) a[i] = in();
    for (int i = 1; i < n; ++ i)
    {
        int x = in(), y = in();
        addedge(x, y); addedge(y, x);
    }
    DFS1(1); DFS2(1, 1);
    init(1); build(1, 1, n);
    Matrix ret;
    while (m --)
    {
        LL x = in(), xx = in(), y = in(), yy = in();
        if (xx == 0) uppath(x, INF); else uppath(x, -INF);
        if (yy == 0) uppath(y, INF); else uppath(y, -INF);
        ret = query(1, 1, n, id[top[1]], id[btm[1]]) * I;
        if (xx == 0 && yy == 0 && min(ret.val[0][1], ret.val[1][1]) > INF) printf("-1\n");
        else printf("%lld\n", min(ret.val[0][1], ret.val[1][1]) + (xx + yy) * INF);
        if (xx == 0) uppath(x, -INF); else uppath(x, INF);
        if (yy == 0) uppath(y, -INF); else uppath(y, INF);
    }
    return 0;
}

还可以直接套用最大全独立集, 不过容易写错.

上一篇： Bullet Gof6DConstrants axis limit

下一篇： Recast Settings Uncovered

动态DP

动态DP

最大权独立集

NOIp2019 D2T3 保卫王国

MyBatis从入门到精通(八)：MyBatis动态Sql之foreach标签的用法

Android 中使用 dlib+opencv 实现动态人脸检测

利用jQuery动态设置单选框的选中

js词法作用域和动态作用域

Windows 10将抛弃动态磁贴！

详解Python中DOM方法的动态性

jQuery动态添加li标签并添加属性和绑定事件方法

关于SEO行业多方面动态关系的解析

Android 图片切换器（dp、sp、px）的单位转换器

JVM中的动态语言支持简介

动态DP

动态DP

最大权独立集

NOIp2019 D2T3 保卫王国

MyBatis从入门到精通(八)：MyBatis动态Sql之foreach标签的用法

Android 中使用 dlib+opencv 实现动态人脸检测

利用jQuery动态设置单选框的选中

js词法作用域和动态作用域

Windows 10将抛弃动态磁贴！

详解Python中DOM方法的动态性

jQuery动态添加li标签并添加属性和绑定事件方法

关于SEO行业多方面动态关系的解析

Android 图片切换器（dp、sp、px） 的单位转换器

JVM中的动态语言支持简介

Android 图片切换器（dp、sp、px）的单位转换器