传送门 ddpddpddp模板题. 题意简述:给你一棵树,支持修改一个点,维护整棵树的最大带权独立集. 思路: 我们考虑如果没有修改怎么做. 貌似就是一个sbsbsb树形dpdpdp,fi,0f_{i,0}fi,0​表示不选iii的最大值,fi,1f_{i,1}fi,1​表示选iii的最大值. 那么可以这样从iii的儿子vvv转移过来: fp,0+=max{fv,0,fv,1},fp,1+=fv,0f_{p,0}+=max\{f_{v,0},f_{v,1}\},f_{p,1}+=f_{v,0}f

动态DP其实挺简单一个东西. 把DP值的定义改成去掉重儿子之后的DP值. 重链上的答案就用线段树/lct维护,维护子段/矩阵都可以.其实本质上差不多... 修改的时候在log个线段树上修改.轻儿子所在重链的线段树的根拿去更新父亲的DP值. #include <cstdio> #include <algorithm> , INF = 0x3f3f3f3f; template <class T> inline void read(T &x) { x = ; char

题意 题目链接 Sol 动态dp板子题.有些细节还没搞懂,待我研究明白后再补题解... #include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 1e5 + 10, INF = INT_MAX; template<typename A, typename B> inline bool chmax(A &x, B y) { return x < y ? x = y

\(\color{#0066ff}{ 题目描述 }\) 给定一棵\(n\)个点的树,点带点权. 有\(m\)次操作,每次操作给定\(x,y\),表示修改点xx的权值为\(y\). 你需要在每次操作之后求出这棵树的最大权独立集的权值大小. \(\color{#0066ff}{输入格式}\) 第一行,\(n,m\)分别代表点数和操作数. 第二行,\(V_1,V_2,...,V_n\),代表\(n\)个点的权值. 接下来\(n-1\)行,\(x,y\),描述这棵树的\(n-1\)条边. 接下来\(m\

是动态dp的板子 大致思想就是用g[u]来表示不包含重链转移的dp值,然后用线段树维护重链,这样线段树的根就相当于这条重链的top的真实dp值 每次修改的时候,修改x点会影响到x到根的真实dp值,但是只会影响到每条重链的低端点的dp值,相当于在log个线段树上单点修改 #include<iostream> #include<cstdio> using namespace std; const int N=200005; int n,m,a[N],h[N],cnt,de[N],fa[

题目描述 给定一棵 n 个点的树,点带点权. 有 m 次操作,每次操作给定 x,y,表示修改点 x 的权值为 y. 你需要在每次操作之后求出这棵树的最大权独立集的权值大小. 输入格式 第一行有两个整数,分别表示结点个数 n 和操作个数 m. 第二行有 n 个整数,第 i 个整数表示节点 iii 的权值 ai. 接下来 (n−1) 行,每行两个整数 u,v,表示存在一条连接 u 与 v 的边. 接下来 m 行,每行两个整数 x,y,表示一次操作,修改点 x 的权值为 y. 输出格式 对于每次操作,

[模板]"动态 DP"&动态树分治 第一道动态\(DP\)的题,只会用树剖来做,全局平衡二叉树什么的就以后再学吧 所谓动态\(DP\),就是在原本的\(DP\)求解的问题上加上修改操作,从而使得问题变成动态的问题 这道题的问题就是普通的树形\(DP\)上加上了修改点权的操作 题意: 给定一棵 \(n\) 个点的树.\(i\) 号点的点权为 \(a_i\).有 \(m\) 次操作,每次操作给定 \(u\),\(w\),表示修改点 \(u\) 的权值为 \(w\).你需要在每次操作

目录 前置知识 全局平衡二叉树 大致介绍 建图过程 修改过程 询问过程 时间复杂度的证明 板题 前置知识 在学习如何使用全局平衡二叉树之前,你首先要知道如何使用树链剖分解决动态DP问题.这里仅做一个简单的回顾,建议在有一定基础的情况下看. 首先,维护序列的动态DP我们就不说了,这里只讨论树上的动态DP问题. 然后,目前个人感觉,动态DP往往有一些奇怪的特征. 一般问题是支持动态修改某一个点的权值,以及询问根节点的(也就是全局的)或者是某一个子树的DP值. 而通常是从静态的情况下入手,写出一个结构

题目:https://www.luogu.org/problemnew/show/P4719 关于动态DP似乎有猫锟的WC2018论文,但找不见:还是算了. http://immortalco.blog.uoj.ac/archive 动态DP大概就是求这样的问题. 把轻儿子对自己的转移值写进矩阵 g 里,重新定义一下乘法运算,自己的值矩阵 f 就是重儿子的 f 乘上自己的 g 了. 树剖的线段树维护区间内的那些 g 的连乘积,则从自己开始到自己所在重链的底端这一段的 g 连乘就是自己的 f 了(

动态DP?动态动态规划? 个人理解:动态DP,就是普通DP加修改操作,然后就变成了个毒瘤题. 直接就着例题写吧. 例题 P4719 [模板]"动态 DP"&动态树分治 求树上最大独立集.要求支持修改点权.n<=1e5. 算法原理 首先不带修的最大独立集是一个NOIP题: \(f[cur][0/1]\) 表示 \(cur\) 选/不选 其子树内(含 \(cur\))的被选点权值和. \[f[cur][0]= \sum max(f[to][0], f[to][1]) \] \

目录 「CF 750E」New Year and Old Subsequence 「洛谷 P4719」「模板」"动态 DP" & 动态树分治 「洛谷 P6021」洪水 「SP 6779」GSS7 「NOIP 2018」「洛谷 P5024」保卫王国 \(\mathcal{Introduction}\) \(\mathcal{Problem~1}\)   给定序列 \(\{a_n\}\),其中 \(a_i\in\mathbb Z\),求其最大子段和(不能为空).   很显然的 DP

题目链接 Luogu P4643 题解 猫锟在WC2018讲的黑科技--动态DP,就是一个画风正常的DP问题再加上一个动态修改操作,就像这道题一样.(这道题也是PPT中的例题) 动态DP的一个套路是把DP转移方程写成矩阵乘法,然后用线段树(树上的话就是树剖)维护矩阵,这样就可以做到修改了. 注意这个"矩阵乘法"不一定是我们常见的那种乘法和加法组成的矩阵乘法.设\(A * B = C\),常见的那种矩阵乘法是这样的: \[C_{i, j} = \sum_{k = 1}^{n} A_{i,

我们经常会遇到一些问题,是一些dp的模型,但是加上了什么待修改强制在线之类的,十分毒瘤,如果能有一个模式化的东西解决这类问题就会非常好. 给定一棵n个点的树,点带点权. 有m次操作,每次操作给定x,y,表示修改点x的权值为y. 你需要在每次操作之后求出这棵树的最大权独立集的权值大小. 如果不带修改,那就是一个最简单是树形dp问题. 我们设一个dp[i][0],dp[i][1]表示以i为根的子树 动态dp能够使用的一个前提就是它的转移是线性的,这样我们就可以用矩阵乘法实现快速转移了. 注意:这里的

不得不承认,去年提高组 D2T3 对动态 DP 起到了良好的普及效果. 动态 DP 主要用于解决一类问题.这类问题一般原本都是较为简单的树上 DP 问题,但是被套上了丧心病狂的修改点权的操作.举个例子,我们来看一道例题. [模板]动态 DP 给定一棵 \(n\) 个点的树.\(i\) 号点的点权为 \(a_i\).有 \(m\) 次操作,每次操作给定 \(u, w\),表示修改点 \(u\) 的权值为 \(w\).你需要在每次操作之后求出这棵树的最大权独立集的权值大小. 我们首先考虑没有修改的情

动态dp初探 动态区间最大子段和问题 给出长度为\(n\)的序列和\(m\)次操作,每次修改一个元素的值或查询区间的最大字段和(SP1714 GSS3). 设\(f[i]\)为以下标\(i\)结尾的最大子段和,\(g[i]\)表示从起始位置到\(i\)以内的最大子段和. \[ f[i]=\max(f[i-1]+a[i],a[i])\\g[i]=\max(g[i-1],f[i]) \] 定义如下的矩阵乘法,显然这满足乘法结合律和分配律. \[ C=AB\\C[i,j]=\max_{k}(A[i,k

学习了一下动态DP 问题的来源: 给定一棵 \(n\) 个节点的树,点有点权,有 \(m\) 次修改单点点权的操作,回答每次操作之后的最大带权独立集大小. 首先一个显然的 \(O(nm)\) 的做法就是每次做一遍树形DP(这也是我在noip考场上唯一拿到的部分分),直接考虑如何优化这个东西. 简化一下问题,假如这棵树是一条链,那就变得很简单了,可以直接拿线段树维护矩阵加速. 可是如果每个点不止有一个儿子呢? 我们首先树剖一下. 设 \(g[i][0]=\sum\limits_{j\in ligh

题目分析: 不难发现可以用动态DP做. 题目相当于是要我求一条路径,所有与路径有交的链的代价加入进去,要求代价最大. 我们把链的代价分成两个部分:一部分将代价加入$LCA$之中,用$g$数组保存:另一部分将代价加在整条链上,用$d$数组保存. 这时候我们可以发现,一条从$u$到$v$的路径的代价相当于是$d[LCA(u,v)]+\sum_{x \in edge(u,v)}g[x]$. 如果是静态的,可以用树形DP解决. 看过<神奇的子图>的同学都知道,叶子结点是从它的儿子中取两个最大的出来,所

[复习]动态dp 你还是可以认为我原来写的动态dp就是在扯蛋. [Luogu4719][模板]动态dp 首先作为一个\(dp\)题,我们显然可以每次修改之后都进行暴力\(dp\),设\(f[i][0/1]\)表示当前考虑\(i\)及其子树内的点,当前这个点是选还是不选时能够得到的最大权值,那么我们可以得到转移:\(f[i][0]+=\max\{f[v][0],f[v][1]\},f[i][1]+=f[v][0]\),其中\(v\)是\(i\)的一个儿子. 那么这样子的复杂度就是\(O(qn)\)

[BZOJ4911][SDOI2017]切树游戏(动态dp,FWT) 题面 BZOJ 洛谷 LOJ 题解 首先考虑如何暴力\(dp\),设\(f[i][S]\)表示当前以\(i\)节点为根节点,联通子树权值和为\(S\)的方案数,转移就是\(FWT\)的卷积,最后只需要把所有的\(f[i][k]\)全部加起来就可以得到最终的答案. 于是这样子的复杂度就是\(O(Qnmlogm)\).但实际上转移的时候不需要\(FWT\)回来,直接拿点值表示的数组做就可以了,这样子可以少一个\(log\). 那么

可以直接套动态dp,但因为它询问之间相互独立,所以可以直接倍增记x转移到fa[x]的矩阵 #include<bits/stdc++.h> #define CLR(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; typedef pair<int,int> pa; ; const ll inf=1e17; inline ll rd(){ ll x=;; ;c=getchar();} +c-',c

题目链接: https://cn.vjudge.net/problem/34398/origin 本题的大意其实很简单,就是找回文串,大致的思路如下: 1. 确定一个回文串,这里用到了自定义的check函数原理如下: 传入le, ri两个值(定义从1开始), s+1 = aaadbccb. a a a d b c c b 1 2 3 4 5 6 7 8 比如,le = 5, ri = 8. 则s[5] == s[8]成立 le++ ri-- 再比较 s[6] == s[7]? 成立 le++,