数位dp

说明：最近在帮高中竞赛教练写讲义，这是本人对讲义中动态 DP 内容的补充解释（因为主要是对知识点的理解，不太容易用通用的语言表述，也不适合作为讲义内容供读者阅读，所以用的是补充注释的形式）。**写的比较抽象也比较初等，仅供意会**。 ## 1. 为什么用矩阵表示转移 我们先从一般的角度，用映射的语言 ......

# DP ## 1. 理论 1. 每个大问题的子问题都是最优的，所以才可以直接记录下来 2. 在下次寻找子问题的最优解时，直接使用 与分治算法不同的是： - 适合 dp 请求的问题，经分解得到的子问题往往不是互相独立的 - 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步求解 ## ......

# 1.定义与原理  # 2.例题一： ## 题目 [Acwing 1081. 度的数量](https:/ ......

## CF1586 f1 f2 Korney Korneevich and XOR 思维+dp ### [题目链接](https://codeforces.com/problemset/problem/1582/F2) ### 题意： 给出长度为n的数组a，对于数组的严格递增子序列，计其异或和为xo ......

## CF1385 F. Removing Leaves 换根dp ### [题目链接](https://codeforces.com/problemset/problem/1385/F) ### 题意： 给你一棵树，有一种操作，选择k个叶子，若叶子节点的父亲相同，则可删去这k个节点，问你最多能操作 ......

前言 最近学了一种新的数位dp的状态表示，打算应用到以前做过的数位dp的题目。如果我们对数$N$进行数位dp，以前的状态定义$f(i,j)$表示所有数位大小为$i$且最高位是数字$j$的数的个数，如果还有其他约束条件那么再补充相应的状态即可。而新的状态定义则是$f(i,1)$和$f(i,0)$，其中 ......

题目链接：https://codeforces.com/problemset/problem/1854/B 题目大致题意： 有n张卡牌从上到下堆叠，每张卡片有锁或不锁俩种状态，一开始第一张是不锁的； 对最上面的卡牌，如果他是不锁的状态，那么可以进行俩种操作： 1：从上到下，将v张被锁的卡牌解锁； 2 ......

### 前置知识 · 单调队列 单调队列顾名思义，一般用于解决 **滑动RMQ**问题。它的原理非常简单。我们维护一个双端队列，这个双端队列 **只维护可能成为区间最值**的元素。 最基础的单调队列，例如滑动窗口。直接依据题意维护即可。 这里提供单调队列模板（STL deque 版） 单调队列模板（ ......

[题单](https://www.luogu.com.cn/training/334619#information) ### 状压 dp 状压 dp是一种非常暴力的算法，它直接记录不同的状态，通过状态进行转移。 状压 dp可以解决 NP 类问题。它的原理是暴力枚举每一种可能的状态。所以它的复杂度是指 ......

# 1.基本定义 树形 $DP$，即在树上进行的 $DP$。由于树固有的递归性质，树形 $DP$ 一般都是递归进行的。 # 2.模板题 [Acwing 285. 没有上司的舞会](https://www.acwing.com/problem/content/287/) ## 思路 我们设 $f(i, ......

### 知道秘密的人数 在第 1 天，有一个人发现了一个秘密。 给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及 ......

### 二叉树的直径 给你一棵二叉树的根节点，返回该树的 **直径** 。 二叉树的 **直径** 是指树中任意两个节点之间最长路径的 **长度** 。这条路径可能经过也可能不经过根节点 `root` 。 两节点之间路径的 **长度** 由它们之间边数表示。 **示例 1：** ``` 输入：roo ......

dp的本质就是图论 状态机dp就是包含多个待选状态，个人感觉就是分层图，每一层是一个状态，不同状态之间有可以相互转化的方法。通过状态和状态之间的关系，来实现状态转移。 本题f[i][j]表示只从前i项中选，f[i][0]表示第i项不进行交换，f[i][1]表示第i项进行交换，达到严格递增情况下所需要 ......

# 这是一道拓扑排序的模板题 ### 0 额. #### 所需的前置知识： - 图论相关的基本概念 - 建图，存图 - 图的遍历 - 非常入门的DP 下面进入正文 #### 1 引入 拓扑排序是一类用于处理 DAG（Directed acyclic graph），即**有向无环图**上的问题。 以这 ......

一直在等学习概率论这门课后再开，但是老师一节课讲的内容我两分钟就能看完，恰巧昨天打了一次比赛遇到求期望DP，是时候学一下了。 概率DP主要用于求解期望、概率等题目。 转移方程有时比较灵活。 一般求概率是正推，求期望是逆推。通过题目可以体会到这点。 ——by kuangbin 首先先推荐几篇参考的论文 ......

# 状压 dp 总结 ### 三进制状压 ### Q&A 1.如果我的当前的dp值需要前两个状态才可以推导出来怎么办? 很简单,既然我们无法舍弃任何一个状态那我们就加一维将它纳入考虑范围之内,就拿 P8756 [蓝桥杯 2021 省 AB2] 国际象棋做列子 我们本列的马最远是可以威胁到前两列的马, ......

换根 dp 一般不会指定根节点，并且根节点的变化会对一些值进行改变。因此我们需要转移根。 换根 dp一般需要预处理一下一个节点的值，然后对于任意节点开始树上dp转移。 所以我们常用两次 dfs，第一次 dfs预处理，第二次 dfs为树上 dp。 一般比较套路。 接下来会给出一个典型例题。 ### 典 ......

[题单](https://www.luogu.com.cn/training/328311#problems) ### 简介 树形 dp，一般常使用 **记忆化搜索** 解决。其关键是找到儿子和父亲之间的转移关系，设计状态。和普通 dp 不同的是，一般先递归处理儿子，再回溯处理父亲。 树形 dp 的 ......

HP DP(Data Protector Manager)上一个刚刚迁移升级的数据库备份作业失败，具体失败信息如下 .................................RMAN-08503: piece handle=c-1684727642-20230822-00 comment=A ......

和`CF149D Coloring Brackets`（B题）一样，都是关于括号的区间DP。 在B题中，有一个细节，就是在枚举断点时枚举到第一个就要`break`，这是为了使每种方案只贡献一次，防止一种方案中有多个符合条件的断点。 此题中，因为序列的字符是不变的，所以直接`break`就行了。 但是 ......

[传送门](https://www.luogu.com.cn/problem/P4719) 简要题意：给定一棵 $n$ 个点的树，点带点权。有 $m$ 次操作，每次操作给定 $x,y$ 表示修改点 $x$ 的权值为 $y$。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 最大权独立集：选若 ......

DP4306F是一款高性能低功耗的单片集成收发机，集成MO核MCU，工作频率可覆盖200MHiz^ 1000MHz。 支持230/408/433/470/868/915频段。该芯片集成了射频接收器、射频发射器、频率综合器、GFSK调制器、GFSK解调器等功能模块。通过SPI接口可以对输出功率、频道选 ......

前言：因为本人 $dp$ 实在太差了，故此挖个新坑。 $dp$ 的一般套路是： * 设计状态，要注意一定要不重不漏，所有能影响到答案的数据都要包含到状态里面。 * 初始化，基本上是第一项 * 转移，要注意无后效性，面面俱到。 * 可以关注数据范围，有时候范围会给我们以提醒。 基本技巧： * 状态设计 ......

## 概念 **最长上升子序列**是指**一个序列中最长的单调递增的子序列**，字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。 求最长上升子序列的长度可以用**线性DP**。 ## 思路 - 1.读入数据，dp[i] 代表以**第 i ......

树是一个由 $n$ 个节点，$n-1$ 条边组成的联通图，图上没有环，其每一条边都是割边。 在树上设计动态规划算法时，一般以节点**从深到浅**的顺序作为 DP 的阶段。大多数时候，采用递归的方式实现树形动态规划。 对于每一个节点 $x$，先对它的每一个子节点进行 DP，回溯时从子节点向 $x$ 进 ......

DP 的效率取决于 $3$ 方面：1. 状态总数 2. 每个状态的决策数 3. 状态转移计算量。这三方面都可以进行优化。 1. 状态总数优化：相当于搜索的剪枝，去除无用状态；使用降维，设计 DP 状态时尽量使用低维的 DP。 1. 决策数量优化：即状态转移方程的优化，减少决策数量，如斜率优化，四边形 ......

## 背包问题 ### 01 背包问题 有 $n$ 件物品和一个容量为 $V$ 的背包，第 $i$ 件物品的体积为 $w[i]$，价值为 $v[i]$。请选择将哪些物品装入背包，使得价值总和最大。 思路：每种物品仅有一件，可以选择放或不放。令 $f[i][j]$ 表示前 $i$ 件物品放入一个容量为 ......

> ⭐️ **本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 \[彭旭锐] 和 [BaguTree Pro](https://www.mdnice.com/writing/85b28c4e60354865a423728e668fc570) 知识星球提问。** > > 学习数据 ......

> ⭐️ **本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 \[彭旭锐] 和 [BaguTree Pro](https://www.mdnice.com/writing/85b28c4e60354865a423728e668fc570) 知识星球提问。** > > 学习数据 ......

不难写出转移方程, $f_{i, j}$表示此时所走过的状态pattern为i, 目前所在城市为j. 则转移方程为: $$ f_{i, j} = min\{f_{i, j}, f_{i - 2^k, k} + a_{k, j}\} $$ k为合法的前继城市, 则$i - 2^k$就是合法的前继状态( ......