动态 DP 入门

问题一

考虑带修改最大子段和的问题：

给一个序列 $a_i$ ，支持
求最大子段和
单点修改

求最大子段和有这样一个贪心做法，即遍历序列，令 $cur=\max(cur+a_i,a_i),ans=\max(ans,cur)$ 。

让我们定义一种新的矩阵运算方式： $(\oplus,\otimes)[AB]_{i,j}=\bigoplus_{k}(A_{i,k}\otimes B_{k,j})$ 。因此我们可以得到

$(\max,+) \begin{bmatrix} a_i & -\infty & a_i\\ 0 & 0 & -\infty\\ -\infty & -\infty & 0 \end{bmatrix} \begin{bmatrix} cur\\ ans\\ 0 \end{bmatrix}= \begin{bmatrix} \max(cur+a_i,a_i)\\ \max(ans,cur)\\ 0 \end{bmatrix}$

这样最后的答案其实是 $\max(ans,cur)$ （不是直接取 $ans$ ，因为 $cur$ 比 $ans$ 多算了一次），初始矩阵

$\begin{bmatrix} -\infty\\ -\infty\\ 0 \end{bmatrix}$

由于矩阵运算具有结合律，因此线段树维护矩阵快速幂同样可以解决本问题。

问题二

考虑带修改带点权树上最大权独立集问题：

给出一棵带点权有根树，支持：
修改点权；
询问一棵子树的最大权独立集。

考虑暴力 DP， $f(i,j)$ 表示以 $i$ 为根的子树， $i$ 是（ $j=1$ ）否（ $j=0$ ）在独立集中，的最大权独立集。容易得到

$f(u,0)=\sum_{v\in Son(u)}\max(f(v,0),f(v,1))\\ f(u,1)=a_u+\sum_{v\in Son(u)}f(v,0)$

可以将转移式等价地写作

$f(u,c)=a_u\cdot c+\sum_{v\in Son(u)}\max(f(v,0),f(v,1)-c\cdot\infty)$

将树链剖分，转化为链上的问题。假设重链上从浅到深第 $i$ 个结点的编号是 $i$ ，且令

$g(i,c)=a_i\cdot c+\sum_{j\in Son(i)-\{i+1\}}\max(f(j,0),f(j,1)-c\cdot\infty)$

表示它的轻儿子的 DP 值，则有

$f(i,c)=g(i,c)+\max(f(i+1,0),f(i+1,1)-c\cdot\infty)$

把 $g(i,c)$ 丢到 $\max$ 里面去就能写成矩乘的形式了：

$(\max,+) \begin{bmatrix} g(i,0) & g(i,0)\\ g(i,1) & -\infty \end{bmatrix} \begin{bmatrix} f(i+1,0)\\ f(i+1,1)\\ \end{bmatrix} = \begin{bmatrix} f(i,0)\\ f(i,1)\\ \end{bmatrix}$

这样，这条重链的矩阵就是它轻儿子的 DP 值了。单点修改的时候，沿着链往上跳，并修改对应的 $g(i,c)$ 。

#include<algorithm>
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
/******************heading******************/
#define int lld
const int N=1e5+5,MTX=2,INF=0x3f3f3f3f,LST=N<<2;

int n,m;
int val[N];

struct qxx{int nex,t;};
qxx e[N*2];
int h[N],le;
void add_path(int f,int t){e[++le]=(qxx){h[f],t},h[f]=le;}

struct mtx{/*{{{*/
    int r,c;
    int w[MTX][MTX];
    mtx(){
        r=c=0;
    }
    mtx(int _r,int _c){
        r=_r,c=_c;
        FOR(i,0,r-1)FOR(j,0,c-1)w[i][j]=-INF;
    }
    mtx(int _r){
        r=c=_r;
        FOR(i,0,r-1)FOR(j,0,c-1)w[i][j]=i==j?0:-INF;
    }
    mtx(int _r,int _c,int _w[MTX][MTX]){
        r=_r,c=_c;
        FOR(i,0,r-1)FOR(j,0,c-1)w[i][j]=_w[i][j];
    }
    mtx operator*(mtx m){
        //assert(c==m.r);
        mtx res(r,m.c);
        FOR(i,0,r-1)FOR(j,0,m.c-1)FOR(k,0,c-1)
            res.w[i][j]=max(res.w[i][j],w[i][k]+m.w[k][j]);
        return res;
    }
    mtx operator*=(mtx m){ return *this=*this*m; }
    void print(){
        FOR(i,0,r-1){
            printf("|");
            FOR(j,0,c-1)if(w[i][j]==-INF)printf("-INF");else printf("%3lld ",w[i][j]);
            printf("|");
            puts("");
        }
        puts("");
    }
};/*}}}*/

mtx tree_mt[N];
int totdfn;

namespace seg{
    mtx mt[LST];
    void pushup(int u){
        mt[u]=mt[u<<1]*mt[u<<1|1];//left multiply
    }
    void build(int u=1,int l=1,int r=totdfn){
        if(l==r)return mt[u]=tree_mt[l],void();
        int mid=(l+r)>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
    mtx query(int L,int R,int u=1,int l=1,int r=totdfn){
        if(L<=l&&r<=R)return mt[u];
        int mid=(l+r)>>1;
        mtx res(MTX);
        if(L<=mid)res*=query(L,R,u<<1,l,mid);
        if(mid<R)res*=query(L,R,u<<1|1,mid+1,r);
        return res;
    }
    void assign(int p,mtx matrix,int u=1,int l=1,int r=totdfn){
        if(l==r)return mt[u]=matrix,void();
        int mid=(l+r)>>1;
        if(p<=mid)assign(p,matrix,u<<1,l,mid);
        else assign(p,matrix,u<<1|1,mid+1,r);
        pushup(u);
    }
}

int dep[N],hvs[N],sz[N],tp[N],bt[N],fa[N],dfn[N];
int f[N][2],g[N][2];
int dfs1(int u,int p){/*{{{*/
    dep[u]=dep[p]+1,sz[u]=1;
    fa[u]=p;
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p)continue;
        sz[u]+=dfs1(v,u);
    }
    return sz[u];
}/*}}}*/
void dfs2(int u,int p,int to){/*{{{*/
    tp[u]=to,bt[u]=u,dfn[u]=++totdfn;
    int mx=0;
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p)continue;
        if(sz[v]>mx)mx=sz[v],hvs[u]=v;
    }
    if(hvs[u])dfs2(hvs[u],u,to),bt[u]=bt[hvs[u]];
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p||v==hvs[u])continue;
        dfs2(v,u,v);
    }
    //printf("u=%lld,hvs=%lld,tp=%lld,bt=%lld\n",u,hvs[u],tp[u],bt[u]);
}/*}}}*/
void dfs3(int u,int p){
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p)continue;
        dfs3(v,u);
        if(v!=hvs[u]) g[u][0]+=max(f[v][0],f[v][1]), g[u][1]+=f[v][0];
        else f[u][0]=max(f[v][0],f[v][1]), f[u][1]=f[v][0];
    }
    g[u][1]+=val[u];
    f[u][0]+=g[u][0],f[u][1]+=g[u][1];
    //printf("u=%-2d,f0=%-3d,f1=%-4d,g0=%-3d,g1=%-3d\n",u,f[u][0],f[u][1],g[u][0],g[u][1]);
    int t[MTX][MTX]={g[u][0],g[u][0],g[u][1],-INF};
    tree_mt[dfn[u]]=mtx(2,2,t);
    //tree_mt[dfn[u]].print();
}

mtx f_mtx(int u){//calculate f[u][0],f[u][1] -> g_mtx[0][0],g_mtx[1][0]
    return seg::query(dfn[u],dfn[bt[u]]);
}
void assign(int u,int v){//val[u]=v
    //printf("assign(%lld,%lld)\n",u,v);
    g[u][1]=g[u][1]-val[u]+v,val[u]=v;
    while(u){
        //printf("u=%lld\n",u);
        int t[MTX][MTX]={g[u][0],g[u][0],g[u][1],-INF};
        seg::assign(dfn[u],mtx(2,2,t));
        u=tp[u];
        mtx a=f_mtx(u);// 当前链顶的 f
        if(fa[u]){
            g[fa[u]][1]=g[fa[u]][1]-f[u][0]+a.w[0][0];
            g[fa[u]][0]=g[fa[u]][0]-max(f[u][0],f[u][1])+max(a.w[0][0],a.w[1][0]);
        }
        f[u][0]=a.w[0][0],f[u][1]=a.w[1][0];
        u=fa[u];
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    FOR(i,1,n)scanf("%lld",&val[i]);
    FOR(i,1,n-1){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add_path(x,y),add_path(y,x);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    dfs3(1,0);
    seg::build();
    FOR(i,1,m){
        int x,y;
        scanf("%lld%lld",&x,&y);
        assign(x,y);
        mtx ans=f_mtx(1);
        printf("%lld\n",max(ans.w[0][0],ans.w[1][0]));
    }
    return 0;
}
/*
 * g[u,0]=sum_{v!=hvs[u]} max(f[v,0],f[v,1])
 * g[u,1]=a[u] + sum_{v!=hvs[u]} f[v,0]
 * f[u,0]=g[u,0]+max(f[u+1,0],f[u+1,1])
 * f[u,1]=g[u,1]+f[u+1,0]
 * f[leaf,0]=g[leaf,0]=0
 * f[leaf,1]=g[leaf,1]=a[leaf]
 */

问题三

带点权 $a_i$ 的有根树上，选择一个点可以覆盖它子树的叶子结点。问覆盖某个子树的叶子结点的最小代价。单点修改

朴素的 DP 是

$f(u)=\min\left(a_u,\sum_{v\in Son(u)}f(v)\right)$

设

$g(u)=\sum_{v\in Son(u),v\ne u\text{'s heaviest son}}f(v)$

则得到

$f(i)=\min\left(a_i,g(i)+f(i+1)\right)$

于是得到

$\begin{bmatrix} g(i) & a_i\\ \infty & 0 \end{bmatrix} \begin{bmatrix} f(i+1)\\ 0 \end{bmatrix} = \begin{bmatrix} f(i)\\ 0 \end{bmatrix}$

问题四

n 个人进行 $n$ 轮游戏，第 $i$ 轮第 $i$ 个人可以选择让 $x=(x+a_i)\bmod n$ 。初始时 $x=0$ ，游戏从编号为 0 的人开始。游戏结束后第 $x$ 个人获胜。对于第 $i$ 个人，只有当 $x$ 变了后必胜，不变不必胜的时候才会选择变，并且这是一个 Common Knowledge。支持单点修改，问谁获胜。

手玩发现，只有当 $x=(i-a_i)\bmod n$ 时，第 $i$ 个人才可能会动。因为每个人都只会想自己赢，不会把别人送赢。因此不能指望后面的人帮他把 $x$ 变成 $i$ 。由此可以推出，如果 $(i-a_i)\bmod n> i$ ，则 $i$ 不可能获胜。因为前面的 $0\sim i-1$ 只会把 $x$ 变成自己，不会变得比自己大。于是我们想到 $i-a_i$ 向 $i$ 连边，这样可以构成一棵树，显然编号为 $0$ 的点是根结点。

沿着树边走到结点 $u$ ，相当于 $u$ 选择变，把 $x$ 从上一个结点编号变成了 $u$ 。于是我们定义 $f_u$ 表示最优策略下 $u$ 是否会动。则显然当 $u$ 的儿子结点都不动时， $u$ 选择动是必胜的：

$f_u=1-\max_{v\in Son(u)}f(v)\\ f_{leaf}=1$

若根结点为 $1$ 则根结点获胜。否则沿着它编号最小的儿子往下走，第一个 $f_u=1$ 的点获胜。如果整颗树的 DP 值都是 $0$ 则根结点也获胜。单点修改相当于修改某个点的父亲，则 LCT 维护动态 DP 即可。

文章目录

问题一

问题二

问题三

问题四

修订记录