首页 > 其他分享 >【DP】动态 DP

【DP】动态 DP

时间:2022-11-04 11:13:22浏览次数:55  
标签:val int max top mid son 动态 DP

准备退役 whk 了,最后学点东西。

不得不承认,CSPS2022 T4 对动态 DP 起到了良好的普及效果。

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

设 \(f_{u,0/1}\) 表示不选/选 \(u\),\(u\) 的子树内的最大权独立集。

不带修改的情况,有

\[f_{u,0}=\sum\max(f_{v,0},f_{v,1}) \]

\[f_{u,1}=val_u+\sum f_{v,0} \]

答案即为 \(\max(f_{1,0},f_{1,1})\)。

如果带修改呢?修改的结点影响的仅是其到根节点的路径。可以用树剖(重链剖分),为啥?

树剖有很好的性质:重儿子的 \(dfs\) 序连续,任意节点到根节点最多经过 \(\log n\) 条轻边。

这启示我们可以把轻儿子的信息合并起来,对于重儿子在跳重链的时候合并。

设 \(g_{u,0/1}\) 表示只考虑轻儿子,且 \(u\) 不选/选的最大权独立集。则有

\[f_{u,0}=g_{u,0}+\max(f_{son_u,0},f_{son_u,1}) \]

\[f_{u,1}=g_{u,1}+f_{son_u,0} \]

\(son_u\) 表示 \(u\) 的重儿子。这样我们还把 \(\sum\) 去掉了。

现在的问题就是如何快速合并和修改了,注意到可以使用广义矩阵乘法实现,有

\[f_{u,0}=\max(g_{u,0}+f_{son_u,0},g_{u,0}+f_{son_u,1}) \]

\[f_{u,1}=\max(g_{u,1}+f_{son_u,0},-\infty) \]

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

注意这里矩阵一定得这么写,因为链头在区间左端,链尾在区间右端,维护的初始信息在叶子结点,所以只能把它放在右边。

怎么合并?废话,重链直接合并,向上跳轻边的时候合并到上一级重链,修改的时候用增量的方式改变父亲代表的矩阵。

点击查看代码
#define pb push_back
const int N=1e5+10,inf=0x3f3f3f3f;

int n,m;
vector<int> e[N];
int siz[N],fa[N],son[N],in[N],out[N],top[N],rnk[N],tim=0;
int f[N][2],a[N];

struct matrix{
    int m[2][2];
    inline matrix operator *(const matrix& b)const{
        matrix res;
        res.m[0][0]=res.m[0][1]=res.m[1][0]=res.m[1][1]=-inf;
        for(int k=0;k<2;++k){
            for(int i=0;i<2;++i){
                for(int j=0;j<2;++j){
                    res.m[i][j]=max(res.m[i][j],m[i][k]+b.m[k][j]);
                }
            }
        }return res;
    }
}val[N],mat[N<<2],bef,aft;

void dfs1(int u,int f){
    fa[u]=f,siz[u]=1;
    for(int v:e[u])if(v!=f){
        dfs1(v,u);siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){//预处理出初始矩阵
    top[u]=t,rnk[in[u]=++tim]=u,out[t]=max(out[t],tim);
    //out 表示链顶所在链的链底
    f[u][0]=0,f[u][1]=a[u];
    val[u].m[0][0]=val[u].m[0][1]=0;
    val[u].m[1][0]=a[u];val[u].m[1][1]=-inf;
    if(son[u]){
        dfs2(son[u],t);//重儿子不用算到 g 里面
        f[u][0]+=max(f[son[u]][0],f[son[u]][1]);
        f[u][1]+=f[son[u]][0];
    }
    for(int v:e[u])if(v!=fa[u]&&v!=son[u]){
        dfs2(v,v);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
        val[u].m[0][0]+=max(f[v][0],f[v][1]);
        val[u].m[0][1]=val[u].m[0][0];
        val[u].m[1][0]+=f[v][0];
    }
}

#define ls p<<1
#define rs p<<1|1
void build(int p,int l,int r){
    if(l==r)return mat[p]=val[rnk[l]],void();
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    mat[p]=mat[ls]*mat[rs];
}
void modify(int p,int l,int r,int pos){
    if(l==r)return mat[p]=val[rnk[pos]],void();
    int mid=(l+r)>>1;
    if(pos<=mid)modify(ls,l,mid,pos);
    else modify(rs,mid+1,r,pos);
    mat[p]=mat[ls]*mat[rs];
}
matrix query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return mat[p];
    int mid=(l+r)>>1;
    if(qr<=mid)return query(ls,l,mid,ql,qr);
    if(ql>mid)return query(rs,mid+1,r,ql,qr);
    return query(ls,l,mid,ql,mid)*query(rs,mid+1,r,mid+1,qr);
}

void change(int u,int k){
    val[u].m[1][0]+=k-a[u];a[u]=k;
    while(u){
        bef=query(1,1,n,in[top[u]],out[top[u]]);
        modify(1,1,n,in[u]);
        aft=query(1,1,n,in[top[u]],out[top[u]]);
        u=fa[top[u]];
	//向上跳轻边用增量法修改,注意矩阵中的元素代表的意义以及转移式
        val[u].m[0][0]+=max(aft.m[0][0],aft.m[1][0])-max(bef.m[0][0],bef.m[1][0]);
        val[u].m[0][1]=val[u].m[0][0];
        val[u].m[1][0]+=aft.m[0][0]-bef.m[0][0];
    }
}

int main(){
    read(n),read(m);
    for(int i=1;i<=n;++i)read(a[i]);
    for(int i=1,u,v;i<n;++i){
        read(u),read(v);
        e[u].pb(v),e[v].pb(u);
    }dfs1(1,0),dfs2(1,1);build(1,1,n);
    for(int i=1,x,y;i<=m;++i){
        read(x),read(y);
        change(x,y);
        matrix ans=query(1,1,n,in[1],out[1]);
        printf("%d\n",max(ans.m[0][0],ans.m[1][0]));
    }
    return 0;
}

其他例题以后再补吧。

标签:val,int,max,top,mid,son,动态,DP
From: https://www.cnblogs.com/RuntimeErr/p/16857065.html

相关文章

  • 基于gamebased算法的动态频谱访问matlab仿真
    目录一、理论基础二、核心程序三、测试结果一、理论基础随着越来越多的新型无线应用,对频谱资源的需求越来越大。在这种情况下,这是举世公认的认知无线电的出现已经成为......
  • gridpanel header click
    varmyGrid=Ext.Create('Ext.grid.Panel',{renderTo:'shrGrid',renderTo:myGrid,store:myStore,//JSONobjectcolumns:myGrid.columns,//JS......
  • IS-IS动态路由协议笔记(中)路由计算方法
    IS-IS动态路由协议笔记(中)路由计算方法中间系统到中间系统(IS-IS,Intermediatesystemtointermediatesystem,读作“i-sys”)是一种内部网关协议,是电信运营商普遍采用的......
  • aop-动态代理,cglib动态代理,面向切面编程,aop的实现方法
    第三章aop1.动态代理实现方式:jdk动态代理,使用jdk中的Proxy,Method,InvocaitonHanderl创建代理对象。jdk动态代理要求目标类必须实现接口案例结构如下:创建需要被代理的......
  • DPM(Deformable Part Model)的PCA+Starcasscade(Windows)代码整理
    大家好,我是你们的老朋友——泽哥!最近一直没有写博客是因为泽哥最近在忙本科毕业设计。泽哥的本科毕业设计是研究DPM模型的,相信大家也略微了解,DPM模型即DeformablePartMode......
  • asp.net mvc 3.0 动态无损图片压缩,及路由定义
    最新更新:1208211.定义路由2.编写控制器3.编写图片压缩方法4.测试运行---------------------------------------------------1.定义路由,一般写在Globals.cs文件中routes.M......
  • 区间DP
    区间dp\(Part\)\(1\):区间dp?利用一个常见的区间dp问题来寻找其与其他dp的区别。石子合并:先不考虑环上,就只看一条链的情况,要求将\(1\)~\(n\)的石子合并成一颗,每......
  • 线段树动态开点
    点击查看代码#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false);#defineendl'\n'usingnamespacestd;typedeflonglongll;constintMAXN=......
  • #yyds干货盘点# 动态规划专题:打家劫舍(二)
    1.简述:描述你是一个经验丰富的小偷,准备偷沿湖的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能偷相邻的两家,即,如果偷了第一家,就不能再偷第二家,如果偷了第二家,那么就......
  • cegui 动态链接库调用路径
    //----------------------------------------------------------------------------//staticStringgetModuleDirEnvVar(){if(constchar*envModuleDir=getenv(MO......