【模板】动态 DP 学习笔记 | 加强版 题解

Wy_x · 2025-10-24 21:07:04 · 题解

Update：2025/10/28

感谢 Aurie 指出本文的两处错误。已经修改。

致歉：作者是在打代码之前就完成了文字部分，转移方程的锅代码中修了，文字部分没修，在此致歉。

【模板】动态 DP 加强版 题解

该篇为题解。

总文章（动态 dp 学习笔记）同步发表于 cnblogs。

总文章（动态 dp 学习笔记）同步发表于 luogu。

前置知识：

• 简单 dp
• 树链剖分
• 矩阵乘法和广义矩阵乘法

P4719 【模板】动态 DP

本文着重讲下修改的具体过程以及代码实现，蒟蒻花了好长时间才明白。

鏖战一天终于通过了板子题啊啊啊！！！

不带修：简单树上 dp。

考虑不带修改，就是一个平凡的树上最大权独立集问题，简单树上 dp 即可求解。

设 dp[i][0/1] 表示以 i 为根子树中选/不选 i 所得到的树上最大权独立集的大小。

转移是容易的：

带修了！

但是丧心病狂的出题人加上了修改点权！

考虑动态维护这个问题。

发现树剖有一个性质：跳重链至多 O(\log) 次。

设：

\left[ \begin{smallmatrix} 0\ 0\ \end{smallmatrix} \right]

\left[ \begin{smallmatrix} 0\ 0\ \end{smallmatrix} \right]

发现性质不变。

那么有矩阵形式转移：

意义即为从第 i-1 列直接向右走一步，再在第 i 列上下移动，到这一列每一行的距离最小值。

由实际意义，直接使用待定系数法，得到转移矩阵为：

但这是无障碍情况。

考虑（以下情况均需考虑）：

第 2 行第 i 列为障碍：

那么只可能是行 1 \to 1 和 3 \to 3 存在。令 a=z=1，其余为 \infty 即可。

第 1 行第 i 列为障碍：

那么 1 不能到下一列，2 和 3 不能走到 1。令 a=b=c=d=x=\infty。

第 3 行第 i 列为障碍：

那么 3 不能到下一列，1 和 2 不能走到 3。类似的，令 c=f=x=y=z=\infty。

转移矩阵构造完了。

那么考虑：

答案矩阵 B_n 怎么求？

其中 B_0 中的元素均为 0。

然后直接拍上线段树维护区间矩阵连乘积，修改时直接暴力按照规则重构矩阵，非叶子节点矩阵为左 右。

常数较大。可以通过本题。

Code：

#include<bits/stdc++.h>
#define int long long

using namespace std;

inline int read()
{
    int x=0,c=getchar(),f=0;
    for(;c>'9'||c<'0';f=c=='-',c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}
inline void write(int x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9)  write(x/10);
    putchar(x%10+'0');
}

// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif

const int inf=1e18;

const int N=2e5+5;
int n;
char c[N][4];

struct Martix{
    int a[3][3]={};
}t[N<<2],I,I2;

Martix operator*(const Martix &x,const Martix &y)
{
    Martix ans;
    memset(ans.a,0x3f,sizeof(ans.a));
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    for(int k=0;k<3;k++)
    ans.a[i][j]=min(ans.a[i][j],x.a[i][k]+y.a[k][j]);
    return ans;
}

#define lp (p<<1)
#define rp ((p<<1)|1)

Martix Make(int i)
{
    Martix ans;
    ans=I;
    if(c[i][2]=='#')
    {
        ans=I2;
        ans.a[0][0]=ans.a[2][2]=1;
    }
    if(c[i][1]=='#')
    {
        ans.a[0][0]=ans.a[0][1]=ans.a[0][2]=inf;
        ans.a[1][0]=ans.a[2][0]=inf;
    }
    if(c[i][3]=='#')
    {
        ans.a[2][0]=ans.a[2][1]=ans.a[2][2]=inf;
        ans.a[0][2]=ans.a[1][2]=inf;
    }
    return ans;
}

void build(int l,int r,int p)
{
    if(l==r)
    {
        t[p]=Make(l);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,lp);
    build(mid+1,r,rp);
    t[p]=t[lp]*t[rp];

    // cout<<"["<<l<<","<<r<<"] p=\n";
    // for(int i=0;i<3;i++,cout<<"\n")
    // for(int j=0;j<3;j++)
    // cout<<t[p].a[i][j]<<" ";
    // cout<<"\n\n";
}

void change(int l,int r,int x,int p)
{
    if(l==r)
    {
        t[p]=Make(l);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) change(l,mid,x,lp);
    else change(mid+1,r,x,rp);
    t[p]=t[lp]*t[rp];

    // cout<<"["<<l<<","<<r<<"] p=\n";
    // for(int i=0;i<3;i++,cout<<"\n")
    // for(int j=0;j<3;j++)
    // cout<<t[p].a[i][j]<<" ";
    // cout<<"\n\n";

}

signed main()
{
    I.a[0][0]=1;
    I.a[0][1]=2;
    I.a[0][2]=3;
    I.a[1][0]=2;
    I.a[1][1]=1;
    I.a[1][2]=2;
    I.a[2][0]=3;
    I.a[2][1]=2;
    I.a[2][2]=1;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    I2.a[i][j]=inf;
    cin>>n;
    for(int j=1;j<=3;j++)
    for(int i=1;i<=n;i++) cin>>c[i][j];

    int Q=0;
    cin>>Q;
    build(1,n,1);

        // Martix nw=t[1];

        // int ans=nw.a[0][2];
        // if(ans>=1e8) ans=-1;
        // write(ans);
        // putchar('\n');

    while(Q--)
    {
        int x,y;
        cin>>y>>x;
        // cout<<x<<" "<<y<<"\n";
        if(c[x][y]=='#') c[x][y]='.';
        else c[x][y]='#';
        change(1,n,x,1);
        Martix nw=t[1];

        int ans=nw.a[0][2]-1;
        if(ans>=1e8) ans=-1;
        write(ans);
        putchar('\n');

        // cout<<"\n-------------------\n\n";
    }

    return 0;
}