url: https://www.luogu.com.cn/problem/P4095tag: 动态规划，背包DP，进制，枚举思路：多重背包问题为基础，做两次01背包，前一次后一次，之后对于每次询问的id就跳过那个id求可能的最大值。代码：#include <iostream> #include <cstdio> #incl…

url: http://oj.ecustacm.cn/problem.php?id=1370tag: 动态规划思路：使用动态规划的思想，令 f[i][j] 表示在i层楼内，使用j部手机，在使用最佳策略下，最多的测试次数，换句话说就是在i层楼内，使用j部手机最少需要花费的最大的测试次数。对于只有1部手机的情况来说，有几层就要测试几次。对于0层来说，不…

url: https://www.luogu.com.cn/problem/P2851tag:动态规划，背包DP，进制，USACO，2006思路：可以用背包来做。用 f[i] 表示john付i块钱时最少的硬币数，用 g[i] 表示店主找零i块钱时最少的硬币数，对于f来说，因为硬币数量有限所以需要用多重背包来完成。而对于g来说因为硬币无限多，所以可以…

url: https://www.luogu.com.cn/problem/P4158tag:动态规划，递推，枚举，背包DP思路：用 f[i][j] 表示前i块木板粉刷j次最多的正确次数。用 g[i][j][k] 表示第i块木板粉刷j次粉刷前k个格子时最多的正确次数。用 sum[i][j] 表示第i块木板，前j个格子中需要涂成蓝色的有几个。所以可以…

url: https://www.luogu.com.cn/problem/P1453tag:动态规划，图论，基环树，树形DP思路：基环树是一种特殊的图结构，可以看作是在一棵树的基础上加入一条额外的边，从而使图中恰好出现一个环，也称作单环图或唯一环图（unicyclic graph）。其主要特点包括：连通性：基环树是连通图，任意两个顶点之间都有路径…

url: https://www.luogu.com.cn/problem/P1272tag:动态规划，树形DP思路：简单的树形DP和背包结合。令 f[u][j] 表示以u节点为根的子树在需要取出j个节点时最少需要断的边。最后在输出答案的时候在所有节点中选择一个答案最小的，注意选择其他节点为根节点时需要断去父节点和其之间的一条边。最后输出答案即可。…

url: https://www.luogu.com.cn/problem/P3177tag:动态规划，树形DP思路：用 f[u][j] 表示以u为根节点的子树中，恰好有j个黑点时的收益。之后就是和分组背包类似的思路，对于每一个相连的节点，由当那个节点取k个黑点时更新过来，在不同的k值之间取一个最大值。使用 (k * (m - k) + (s[v]…

url: https://www.luogu.com.cn/problem/P4170tag:字符串，动态规划，枚举，区间DP思路：使用 f[i][j] 表示从i到j这个区间中如果要涂到规定的情况，最少需要的涂色次数。因为有区间，所以可以使用区间DP，对于每一各区间i到j来说如果第i个字符和第j个字符相同，则 f[i][j] 可以从 f[i][j …

url: https://www.luogu.com.cn/problem/UVA1629tag:动态规划，枚举，前缀和思路：用 dp[lx][ly][rx][ry] 来记录某一个区间中，为使每一块蛋糕都有樱桃的最小代价。使用dfs来枚举每一种可能性。使用记忆化搜索来减少时间。前缀和快速计算出某一块区域樱桃的数量。代码：#include <i…

url: https://www.luogu.com.cn/problem/P3621tag:动态规划，树形DP思路：用 tr[u][0/1] 来存二叉树。做两次dfs第一次求出最大的深度和最小的深度，如果相差大于1直接输出-1。第二次dfs从下到上递归，设计返回值为0/1/2分别表示都是浅层，都是深层和混合。当左边为浅层，右边为深层或者左边为混合…