dp

树的数量 题目其实挺简单的，难点在于状态的设计（其实也没多难）。 令 $f_i$ 表示 $i$ 个点的 $m$ 叉树的数量，发现无法转移。设 $g_{i,j}$ 表示根节点所在子树内有 $i$ 个节点，$j$ 个儿子（儿子所在子树可以为空）。可以写出转移方程：$g_{i,j}=\sum\limits ......

https://www.luogu.com.cn/problem/P8742 输入 #1复制 3 1 4 6 输出 #1复制 10 #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,L ......

https://www.luogu.com.cn/problem/P1026 这题的idea首先是直接暴力枚举k，发现会t，遂想到dp 用 $dp[i][k]$ 表示 前 $i$ 个数形成了 $k$ 段数字的最大答案 注意一个比较坑的点是可能同一个位置会有多个单词开始，但是只计数一个 eg： 1 2 ......

题目分析： 就借助这个题稍微说一下 $dp$ 套 $dp$。 对于 $dp$ 套 $dp$ 其解决的问题是：若给定某一具体情况则答案十分好求，现要求对于所有的情况的答案进行统计。 这类问题我们一般称解决这个具体情况的 $dp$ 为内层 $dp$，而对于所有情况进行统计的 $dp$ 为外层 $dp$。 ......

D. Fragmentation merging https://codeforces.com/gym/103104/problem/D 题意 给定一个长度为n（$n<=5e3$）的排列 每次操作可以选择两个不相交的区间，如果两个区间并起来的新区间是连续的一段数($max - mi + 1 = le ......

分割等和子集 给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。 Link 错误思路 TLS的思路： 记录下所有子集在mp中，但是会造成超时 class Solution { public: bool canPartition(vector<int>& nums) { ......

期望 dp。 LG 传送门 自己的做法时间上过不去，且没有运用期望的优越性。 Solution 重新梳理一下思路。 首先一定要注意，求的是期望！而不是单纯的总权值。 那么对这道题，我们可以转化为：$f_i$ 表示，经过这一位之后，期望总分数增加了多少期望分。 即，若假定所求答案为 $ans_i$，输 ......

把最近做的dp都放在这里，我dp真的是烂到极点，当然别的也做不好，什么都不会（大哭 难度乱序 https://atcoder.jp/contests/abc145/tasks/abc145_f 很多细节 https://atcoder.jp/contests/abc147/tasks/abc147_ ......

题目链接 121. 买卖股票的最佳时机 思路 状态转移方程为 $dp[i] = max(0, dp[i - 1], prices[i] - min)$，设置 dp[0] = 0，所以在取最大值的过程中可以省略0，只需要写 dp[i] = Math.max(dp[i - 1], prices[i] - ......

DP4863 电路是一种双声道桥接音频功率放大器。在5V电源电压下，它能向4Ω负载提供2.2W的输出功率，或向3Ω负载提供2.5W的输出功率，THD + N 小于 1 %。此外，它还具有耳机输入端，可驱动立体声耳机，以单端模式工作。DP4863 电路是为提供高保真音频输出而专门设计的。它在使用时只需 ......

题目链接 剑指 Offer 46. 把数字翻译成字符串 思路 这个问题与 dp 中的经典问题“跳台阶”问题十分类似，在跳台阶问题中我们是选择跳一个台阶或者两个台阶，而在这个问题中我们是选择再统计一个字符还是再统计两个字符。所以他们的状态转移方程都包含 $dp[i]=dp[i-1]+dp[i-2]$。 ......

描述 有n堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？ 输入 输入只包含若干组数据。每组数据第一行包含一个正整数n(2<=n<=1 ......

[蓝桥杯 2022 省 A] 爬树的甲壳虫 题目描述 有一只甲壳虫想要爬上一颗高度为 $n$ 的树，它一开始位于树根, 高度为 $0$，当它尝试从高度 $i-1$ 爬到高度为 $i$ 的位置时有 $P_{i}$ 的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。 输入格式 输入第 ......

You're given a non-empty array of arrays where each subarray holds three integers and represents a disk. These integers denote each disk's width, dept ......

F 连通性状压dp 思路 看了dls的讲解后才明白一点点。 状态$dp[i][j][k]$表示到表示到i列，删除了j条边，点i和n-1+i是否联通，对于下一列点， 若当前i和n-1+i连通，则多出来的三条边连任意两条，使得下一列点i+1和n+i连通，否则下一列点不连通。 若当前点i和n-1+i不连通 ......

最近开始跟着力扣的官方题单开始做题，先从动态规划开始做起，以后在此记录每周做的题目，做总结。 基本思路 动态规划利用递推或递归来解决问题，通常这个问题可以被拆分成相同的小问题，我们通过解决一个小问题继而解决更高一层的较大问题，整合其结果一直到原问题上。例如，斐波那契数列就是一个很典型的可以用动态规划 ......

1.A 没什么难度，直接算就可以了。 点击查看代码 #include<bits/stdc++.h> #define int long long #define Yes printf("Yes\n") #define No printf("No\n") #define YES printf("YES\ ......

不同路径 力扣题目链接(opens new window) 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 示例 1： 输入 ......

三角形中最小路径之和 1.题目描述 给定一个三角形 triangle ，找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到 ......

路径的数目 题目： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径 链接 思路： 这是一道基础的DP题目，走到位置(1,1)只 ......

题目链接 https://codeforces.com/problemset/problem/1168/C 题目大意 给定一个数组 $a$，从下标 $x$ 能够转移到下标 $y$ 要满足 $x \lt y$ 且 $a_{p_i}, &, a_{p_{i+1}} > 0$，其中 $&$ 表示逻辑与。多 ......

转移式形如 $\displaystyle f_i = \sum_{f_i > f_j} g(i, j) f_j + \sum_{f_i < f_j} h(i, j) \boldsymbol{f_i}$。 考虑初始化所有 $f_i$ 为正无穷，化一下式子后发现 $f_j > f_i$ 时仅仅个数而非具 ......

原题链接 题意 给定 $n$，$M$。你有 $n$ 台电脑排成一排，你需要依次开启所有电脑。 你可以手动开启一台电脑。在任意时刻，若电脑 $i-1$ 与电脑 $i+1$ 都已经开启 $(1<i<n)$，电脑 $i$ 将立刻被自动开启。你不能再开启已经开启的电脑。 求你有多少种开启电脑的方案。两个方案 ......

神题。yhx 的讲解 非常好、非常自然。 题意： 给定 $c$ 和 $n$ 段长度为 $a_i$ 的弧，每条弧的起点在圆周上均匀随机一个位置，求所有弧的并集覆盖圆周的概率。 $c \leq 50, n \leq 6$ 环上的问题并不好处理，因此寻求链是自然的。钦定一段弧的起点是一段弧的起点看着不错， ......

1. 斐波那契数列$f_i=f_{i-1}+f_{i-2}$ 组合数 $ C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m} $ 2. 数字三角形 给你一个三角形，问从怎么走能够取得最大代价？求和模100时最大的数？必须经过某一点最大的和？ 多一个条件多一维状态 3.最长上升子序 ......

本题为3月21日23上半学期集训每日一题中A题的题解 题面 题目描述 卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D( $2\leq D\leq 100$)英尺。 卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了 ......

导读 ^ _ ^ 何为状态压缩？ 状态压缩的核心是对二进制的理解我们把一个状态表示成二进制从而用一个整数表示出各种状态在dp操作做，我们用位运算的角度去判断并且执行相应的操作 蒙德里安的梦想 思路 如果横着放确定，那么剩下的就是只能竖着放如何表示每行状态，我们将其用二进制去思考，即每个数都是二进制。 ......

树是一个由 $n$ 个节点 $n-1$ 条边所组成的无向无环连通图。 由于每个节点只有一个父亲，可以消除在具体求解中的后效性。 一般情况下，我们会采用dfs的方式一边遍历树一边 dp。 基础树形dp 例题 $1$：P1352 没有上司的舞会 和序列有关的 dp 设状态一般是设成：考虑前 $i$ 种物 ......

导读 ^ _ ^ 数位DP 数位DP，即是对数的每一位进行统计操作的DP问题。 计数问题 思路（分类讨论） 首先，如果一遍遍枚举，显示是不行的，因为1e8次这样，明显会超时。这类问题的关键是分类讨论，以及如何去从划分的角度思考问题。这样一思考，我们的复杂度降至 ：10 (统计数) * 2（划分数）* ......

题目链接 剑指 Offer 62. 圆圈中最后剩下的数字 思路 经典约瑟夫环问题，可以使用找规律的方法进行解决。 以 n = 8, m = 3为例，下面这幅图展示了模拟执行的全过程，用 F(n,m) 表示最后存活的人的索引。 从8个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人 ......