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…

url: https://www.luogu.com.cn/problem/P1284tag:动态规划，贪心，背包DP思路：用 f[k][i][j] 来表示前k块木板能否组成三角形。所以状态转移方程为：f[k][i][j] = f[k - 1][i - a[k]][j] || f[k - 1][i][j - a[k]] || f[k][i][j] …

url: https://www.luogu.com.cn/problem/P4310tag:动态规划，位运算思路：如果用求最长上升子序列的方式来求会超时。这时我们可以观察到因为要满足bi & bi - 1 != 0，所以对于以ai 结尾的数来说，只要是某一个序列末尾的数的某一位和ai 都是1就可以想接。所以可以用一个数列bit来存某一位为1时的最…

url: https://www.luogu.com.cn/problem/P2015tag：树形DP，动态规划思路：用数组f[u, j] 表示以u为根节点使用不超过 j 条边时最大的苹果数量。和背包问题有点不同的是，对于每一个点来说，假如需要用到某一个子节点来更新，则需要与之想连，所以其实是需要预备那个子节点所连的所有边 + 1的边来更新。所以状…

url: https://www.luogu.com.cn/problem/P3478tag:树形DP，POI，2008思路：利用两次dfs，第一次求出以1为根节点时深度和，以及各个节点为根时的子树大小，之后利用第二次dfs求出每个节点为根时的深度和。这个方法称为二次扫描。代码：#include <iostream> #include …