搜 索

动态DP

  • 498阅读
  • 2021年10月16日
  • 1评论
首页 / 学习笔记 / 正文

动态 DP

给定长度为 $n$ 的序列,询问最大子段和

上面这个是不是很好做,只需要设计转移,然后 $\mathcal O(N)$ 转移即可:

$$ f[i]=\max(f[i-1]+a[i],a[i]) $$

但是加上单点修改的操作应该怎么做呢?显然每次都花 $\mathcal O(N)$ 的时间重新 $\text{DP}$ 是不优的,我们考虑如何快速转移。

矩阵转移

此时就可以想到矩阵乘法加速!但是矩阵乘法的运算和这个根本不对啊,没关系,我们重新定义矩阵乘法!

$$ C_{i,j}=\max_{k}(A_{i,k}+B_{k,j}) $$

那么这个也满足结合律吗?只需要手推一下三个的即可(三个的满足,多个肯定满足)

$$ \begin{aligned} \max\bigg(\max(a_{i,j}+b_{j,k})+c_{k,l}\bigg)=\max\bigg(a_{i,j}+\max(b_{j,k}+c_{k,l})\bigg) \end{aligned} $$

假设最后最大值为 $a'+b'+c'$,显然我从上面两种结合方式都可以得到这个答案。如果不可以,就不符合他是最大值这个假设

所以我们现在有了新的运算!矩阵转移也就可以得到了

$$ \begin{aligned} \begin{bmatrix} f_{i-1}\\0 \end{bmatrix} *\begin{bmatrix} a_i&a_i\\ -\infty&0 \end{bmatrix}=\begin{bmatrix} f_{i}\\0 \end{bmatrix} \end{aligned} $$

于是我们愉快地维护区间矩阵乘法就好了!

树上动态 DP

于是有些毒瘤出题人会把动态 $\text{DP}$ 出到树上。如果最大子段和出到树上我们还方便维护,直接树剖即可,但是有些题不简单

给定一棵 $n$ 个点的树,求最大权独立集,$m$ 次操作,每次把 $x$ 的点权修改为 $v$

P4719 【模板】"动态 DP"& 动态树分治

这个就是洛谷动态 $\text{DP}$ 的模板题了。和上面的同样都是树,有什么不一样呢?答案就是这个 $\text{DP}$ 转移会涉及到所有儿子节点

以下设 $f_{i,1/0}$ 为当 $i$ 选 / 不选时候子树最大权独立集。所以我们显然就有

$$ \begin{aligned} f_{i,0}&=\sum_{j\in son}\max(\ f_{j,0}\ ,\ f_{j,1}\ )\\ f_{i,1}&=\sum_{j\in son}f_{j,0} \end{aligned} $$

怎么办呢,这个看起来好像一下子转移不了。考虑重链剖分的性质,每次我改变某个点的值,他所在的链的轻儿子答案是不会改变的,能不能好好利用这个呢?答案是可以的。我们设 $g_{i,0/1}$ 为 $i$ 不选 / 选时候,他所有轻儿子的贡献。具体来讲:

$$ \begin{aligned} g_{i,0}&=\sum_{j\in light\ son}\max(\ f_{j,0}\ ,\ f_{j,1}\ )\\ g_{i,1}&=\sum_{j\in light\ son}f_{j,0} \end{aligned} $$

那么转移就变成了(设 $son$ 为重儿子)

$$ \begin{aligned} f_{i,0}&=g_{i,0}+\max(f_{son,0},f_{son,1})\\ f_{i,1}&=g_{i,1}+f_{son,0} \end{aligned} $$

这样就可以写转移矩阵了。

$$ \begin{aligned} \begin{bmatrix}f_{son,0}\\ f_{son,1} \end{bmatrix}* \begin{bmatrix}g_{i,0}&g_{i,0}\\ g_{i,1}&-\infty \end{bmatrix}=\begin{bmatrix}f_{i,0}\\ f_{i,1} \end{bmatrix} \end{aligned} $$

于是大体的流程就是每次修改一个点,然后沿着重链向上跳,更新区间矩阵乘积就行了

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  a) for(int i=1,i##end=a;i<=i##end;i++)
using namespace std;
const int N=5e5+9;
inline int read(){
    int f=0,x=0;
    char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
struct matrix{int a[2][2];
    matrix(){memset(a,0,sizeof a);}
    matrix operator*(const matrix x){
        matrix c;
        For(i,0,1)For(j,0,1)For(k,0,1)
            c.a[i][j]=max(c.a[i][j],a[i][k]+x.a[k][j]);
        return c;
    }
};
struct edge{int pre,to;}e[2*N];int last[N],cnt;
void add(int x,int y){e[++cnt].pre=last[x];
    e[cnt].to=y;
    last[x]=cnt;
}
int fa[N],sz[N],dfn[N],son[N],idx,top[N],deep[N];
void dfs1(int x,int f){fa[x]=f;sz[x]=1;
    for(int i=last[x];i;i=e[i].pre){int to=e[i].to;if(to==fa[x])continue;
        dfs1(to,x);sz[x]+=sz[to]; 
        if(sz[to]>sz[son[x]])son[x]=to;
    }
}
void dfs2(int x,int f,int topf){dfn[x]=++idx;top[x]=topf;
    deep[topf]=idx;
    if(son[x])dfs2(son[x],x,topf);
    for(int i=last[x];i;i=e[i].pre){int to=e[i].to;if(to==fa[x]||to==son[x])continue;
        dfs2(to,x,to);
    }
}
matrix t[N<<2],A[N];
struct tree{#define ls (p<<1)
    #define rs (p<<1|1)
    void push_up(int p){t[p]=t[ls]*t[rs];}
    void add(int p,int l,int r,int &x){if(l==r){t[p]=A[l];return;}
        int mid=(l+r)>>1;
        if(mid>=x)add(ls,l,mid,x);
        else add(rs,mid+1,r,x);
        push_up(p);
        return;
    }
    matrix get(int p,int l,int r,int nl,int nr){if(nl<=l&&r<=nr){return t[p];}
        int mid=(l+r)>>1;
        if(nr<=mid)return get(ls,l,mid,nl,nr);
        if(nl>mid)return get(rs,mid+1,r,nl,nr);
        return get(ls,l,mid,nl,nr)*get(rs,mid+1,r,nl,nr);
    }
}T;
int n,m,a[N];
void change(int x,int v){if(v==a[x])return;
    A[dfn[x]].a[1][0]+=v-a[x];a[x]=v;
    matrix odt,now;
    while(x){odt=T.get(1,1,n,dfn[top[x]],deep[top[x]]);
        T.add(1,1,n,dfn[x]);
        now=T.get(1,1,n,dfn[top[x]],deep[top[x]]);
        assert(deep[top[x]]);
        x=fa[top[x]];
        A[dfn[x]].a[0][0]+=max(now.a[0][0],now.a[1][0])-max(odt.a[0][0],odt.a[1][0]);
        A[dfn[x]].a[0][1]+=max(now.a[0][0],now.a[1][0])-max(odt.a[0][0],odt.a[1][0]);
        A[dfn[x]].a[1][0]+=now.a[0][0]-odt.a[0][0];
    }
}
signed main(){n=read(),m=read();
    rep(i,n)a[i]=read();
    rep(i,n-1){int x=read(),y=read();
        add(x,y);add(y,x);
    }
    dfs1(1,0);dfs2(1,0,1);
    rep(i,n){int v=a[i];a[i]=0;
        change(i,v);
    }
    rep(i,m){int x=read(),v=read();
        change(x,v);
        printf("%lld\n",max(A[0].a[0][0],A[0].a[1][0]));
    }
    return 0;
}


评论区
酱溶解 2021年12月13日 21:13
回复

太强了,一看就懂 QwQ

avatar