url: https://www.luogu.com.cn/problem/P1273tag:动态规划，树形DP，背包DP思路：用 f[u][j] 表示第u个节点选择j个用户时的盈利数。使用分组背包的思想。状态转移方程为 f[u][k] = max(f[u][k], f[u][k - l] + f[j][l] - w[i]) 其中w表示如果将节点j…

url: https://www.luogu.com.cn/problem/P3205 tag: 动态规划，区间DP，2010思路：利用区间DP来做。设 f[i][j][0] 表示区间i到j中i从左边进入区间的情况， f[i][j][1] 表示区间i到j中j从右边进入区间的情况。当i从左边进去时，上一个区间应该是 i + 1 到 j ，所以只有当 …

url: https://www.luogu.com.cn/problem/P2986tag:动态规划，树形DP，USACO，2010思路：可以参考 洛谷P3478 POI 2008 STA-Station 都是要求出当某一个节点为根时其他点到这个根的距离，我们可以用一次dfs来求出以任意选的一个节点作为根节点时的答案，比如选择节点1为根节点。然后…

url: https://www.luogu.com.cn/problem/P1040tag:动态规划，递归，枚举，区间DP，NOIP提高组，2003思路：使用区间dp的思路，令 f[i][j] 为节点i到节点j之间最大的加分，并用 root[i][j] 记录下这段区间的根节点。之后遍历每一种可能的区间，依据题目的公式更新数组f记录root最后得出…

url: https://www.luogu.com.cn/problem/P1282tag:动态规划，枚举，背包DP思路：用 f[i][j] 表示用前i块多米诺骨牌形成的差值为j时旋转次数。因为差值的范围是-5000-5000，所以数组加一个5000的偏移量。状态转移方程为 f[i][j + p] = min(f[i - 1][j - (a[i]…

url: https://www.luogu.com.cn/problem/P2014tag:动态规划，树形DP，CTSC/CTS，1997思路：和背包比较像，但是有一点区别的是对如果某个节点要选，也需要将其选不同数量节点的情况，分别更新，也就是说不知道每个点的“体积”是多少。因为要选一门课需要将其有依赖的课也选。所以需要从小更新到大。如果将0也算…

url: https://www.luogu.com.cn/problem/P5322tag:动态规划，背包DP思路：读入的时候反着读，用 a[i][j] 来表示第i座城第j个人出的兵。然后对每座城中的s种出兵的方式排序，得到 a[i][j] 表示第i座城前j个出兵最多的人出的兵。然后用分组背包的方式，每一座城每种出兵数量，用那座城的每一个前k个玩…

url: https://www.luogu.com.cn/problem/P1156tag:动态规划，排序，背包DP思路：对于每一个垃圾来说，为了不去处理时间，可以按照时间顺序排列，之后只要关注两个属性，一个是高度，一个是时间。定义 f 数组，表示当前高度下生存的时间。每次更新先是判断当前高度能否等到这个垃圾，然后判断如果堆起来能不能逃出去，能的…

url: https://www.luogu.com.cn/problem/P2340tag:动态规划，背包，USACO， 2003思路：可以转化为01背包问题来做，因为每个奶牛都只有选和不选两种状态。对于背包问题，需要考虑三个属性，一个是背包容量，一个是体积，还有一个是价值。在这道题中，iq和eq是等价的属性，所以可以一个当作体积，另外一个当作价…

url: https://www.luogu.com.cn/problem/P4084tag: 动态规划，树形DP，USACO，2017思路：用树形DP来解决。定义数组 f[i][k] 表示以i为根节点且i涂的颜色为k时的方案数。然后根据k的不同分别更新即可。最后答案输出以1为根节点时3个颜色方案数之和（以其他节点为根节点也可以）。代码：#incl…