数位dp

思路 ; 明显的是, 后一个 i 要从前面一个进行更新, 利用dp easy版本 ai <=200, 发现当 n>=300 时, 对他是没有影响的, 这样比较好记录 ans进行更新, 利用数据结构处理 hard 版本 拆位, 利用字典树dp , 把参数变成相同的参数, a[i] 和 i , (比大小 ......

题意：某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀 ......

题意：给出一棵无向树，求树的直径，即树上两点之间的最长距离 分析：两种解法 解法1：先任取一个点，找到距离该点最远的点u，再找到距离u最远的点v，那么u和v之间的路径就是一条直径。 证明：只要找到了树的直径的一个端点，再从该点找到最远点就一定是直径的另一个端点。所以只需要证明第一次找到的最远点u就是 ......

题目描述 给定一颗 \(n\) 个节点的完全二叉树，每个点有权值 \(a_i \in [1,m]\)，定义从 \(i\) 到 \(j\) 的路径的权值 \(s_{i,j}\) 为路径上的最大点权。 求所有树（\(n^m\) 种点权）的 \(\sum_{i=1}^n \sum_{j=i}^n s_{i ......

题目 F - Fuel Round Trip 总结 关键在于状态的定义。因为每个位置尽可加油一次，因此往返会相互影响，因而必须考考虑状态中定义去时经过此地的油量j与回时经过此地的油量k，这样才能成功转移； 此外，本题状态转移比较奇特，相邻两个位置的状态的转移，在时间上包含去和回两个不同的时刻，较难理 ......

首先状态表示，对于每个节点来说，都有选择或者不选择两种状态，父亲节点的状态由子节点状态推算而来，比如我们选择了子节点，那么父亲节点肯定不能选择，如果我们不选择父亲节点，那么子节点可以选择也可以不选择。状态表示完成了，接下来就是状态转移。 我们假设dp[root][0]是未选择该节点产生的价值，dp[ ......

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode ......

算法刷题系列上期： 递归、栈/队列、树、回溯、DP（8.29） 数组指针、前缀和/差分/树状数组、滑窗/单调队列/滚动哈希、二分（8.13） 链表题（8.29） 目录动态规划基础状态状态转移函数题目三角形最小路径和 动态规划基础 状态 状态转移函数 题目 三角形最小路径和 时间：3ms 击败 77% ......

原题链接：https://www.luogu.com.cn/problem/P4316 这题是经典的概率dp题，通常看到的题解都是逆推的做法，实际上理解了题目的含义后发现逆推其实是正推的一种特殊情况而已 正推做法： 定义dp[i]表示从1~i的路径长度的期望，那么dp[1] = 0，答案就是dp[n ......

#include<bits/stdc++.h> using namespace std; int n,m,a[505],f[510][110],inf; int s[505],t[505]; int main() { std::ios::sync_with_stdio(false); cin>>n> ......

洛谷传送门 AtCoder 传送门 人生中第一道 AtCoder 问号题。 设 \(P = 998244353\)。 注意到 \(f(T)\) 的定义式中，\(\frac{1}{n}\) 大概是启示我们转成概率去做。发现若把 \(\frac{1}{n}\) 换成 \(\frac{1}{n - 1}\ ......

P8946 The Lost Symbol 这种类型的 dp 的特点就是大部分转移形如 \(f(i,j)\rightarrow f(i+1,j+1)\) 之类的，并且当以上转移出现时原数组被清空，这就可以用一个 deque 来维护，然后对于全局赋值/全局加，需要对每个位置维护一个时间戳，并记录上一次 ......

一道问号题，AT 赛场上没人通过。其实是联考题 这道题十分有意思，做法很简单但是要想到是极其困难的。考场上我也拿着推了很久猜测这个式子的组合意义，擦到了正解的一些边。然而正解的思想还是太反直觉了。 首先题目中的式子实际上是让我们对树上的边建一颗笛卡尔树，然后计算笛卡尔树所有子树大小 +1 的倒数乘积 ......

一家公司里有 n 个员工，他们的编号分别是 1 到 n ，其中 1 号员工是公司 CEO，CEO 在公司里没有上司。除了 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。i 号员工来参加舞会会为大家带来 ai 点快乐值。现在我 ......

题目链接：Travel Plan 题目大意：\(n\) 个点的完全二叉树，每个点可以分配 \(1 \sim m\) 的点权，定义路径价值为路径中最大的点权，求所有路径的价值和。 对于任意长度（这里主要指包括几个节点）的路径 \(t\)，最大点权不超过 \(k\) 的方案数有 \(k^t\) 个， 因 ......

（题目传送门） 什么奇奇怪怪的 \(\rm dp\) 如果要选择 \([i,j]\) 这一段，则它不能被其它的包含，也不能包含其它的。因此前面的选择起点得小于 \(i\)，终点得小于 \(j\) 所以设 \(f_{i,j}\) 表示起点不超过 \(i\)，终点不超过 \(j\) 的最大值，则有 \[ ......

题单 小G有一个大树 #include <bits/stdc++.h> using namespace std; #define int long long int32_t main() { ios::sync_with_stdio(0), cin.tie(0); int n; while (cin ......

一些写过题解的题我就直接挂连接了。 [NOIP2018 提高组] 货币系统 题目描述： 在网友的国度中共有 \(n\) 种不同面额的货币，第 \(i\) 种货币的面额为 \(a[i]\)，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 \(n\)、面额数组为 \(a[1..n]\) 的 ......

P5664 题目描述： Emiya 是个擅长做菜的高中生，他共掌握 \(n\) 种烹饪方法，且会使用 \(m\) 种主要食材做菜。为了方便叙述，我们对烹饪方法从 \(1 \sim n\) 编号，对主要食材从 \(1 \sim m\) 编号。 Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主 ......

DM：data minus 负， DP：data plus 正。 VCC是电源5V(红色线）， DM是USB的数据线D-（白色线）， DP是USB的数据线D-+（绿色线）， GND是地（黑色线），； USB插头线一般的排列方式是VCC、 D- 、D+、GND。 Digital Positive & ......

CF258D 题目描述： 有一个长度为 \(n\) 的排列，有 \(m\) 次操作，操作为交换两个数 \(a,b\) ，每次操作都有 \(50\%\) 的概率进行，求进行 \(m\) 次操作后期望逆序对个数 \(n,m\le1000\) 题目分析： 看到 \(n\) 和 \(m\) 都只有 \(10 ......

[USACO12FEB] Nearby Cows G 题目描述 给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。 输入格式 第一行两个正整数 \(n,k\)。 接下来 \(n-1\) 行，每行两个正整数 \(u,v\)，表示 \(u ......

写代码三要素：边界、目标、转移 DP要求：无后效性 Mr. Young's Picture Permutations 要求从左到右和从上到下都递减 首先肯定按顺序加入 从左到右很明确，加到最右边 从上到下怎么维护？ 其实就是这一行加完之后不超过上一行就行 发现行数很少，直接变成状态 \(dp[b_1 ......

[CTSC1997] 选课 题目描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 \(N\) 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学 ......

CF101E Candies and Stones Link&Submission. DP 的状态设计和转移都是显然的，唯一的问题在于需要输出方案，而这题卡空间。会发现如果用 bitset 存下所有位置的转移，空间刚好多了一点点。所以考虑分两次，第一次只存后 10000 行的转移，然后从最终状态倒退 ......

字面意思。 # 恨妻不成7 [传送门](http://oi.nks.edu.cn/zh/Problem/Details?cid=2440&tid=D) 前面的限制按照题意模拟即可，然后考虑维护平方和的常用手段： 本来是 $\sum a^2$，变成了 $\sum (a+x)^2=\sum a^2+2a ......

`2023-08-22 10:55:44` # 前言 注：这场比赛全是 dp 题，时长 3 小时。 第一眼看到 A 题这种奇葩题面直接跳了，感觉不是自己这种成分能写的，结果我旁边两个呆呆鸟 zyx,cf 居然觉得我直接上来把 A 秒了，然后他们死磕 A 题嗑了两个多小时？？？离谱。 最后我只 A 了 ......

`2023-07-24 20:16:31 AT_dp_v 题解` [AT_dp_v Subtree](https://www.luogu.com.cn/problem/AT_dp_v) # 思路 考虑树形 dp，假设根左右子树的连通块已经算出来了，我们用 $f[x]$ 表示强制将 $x$ 染色，$x ......

这是一道比较板子的数位 dp 。 首先观察到 $k$ 很大，肯定不能用枚举的方法求，然后就考虑用数位 dp 。对于这道题来说，我们可以在用记忆化搜索做数位 dp 的时候存一个当前各数位之和对 $d$ 取余的余数，当把数填完之后判断余数是否为 $0$ 就能判断这个数是否符合条件。 ```cpp #in ......

双倍经验 [CF559C](https://www.luogu.com.cn/problem/CF559C) 前置知识：网格图内任意两点间的路径数量。这个我们可以通过组合数的方法计算出来。假设我们从点 $(1,1)$ 走到点 $(i,j)$，在这个过程中我们的移动步数是 $|i-1+j-1|=|i+ ......