url: https://www.luogu.com.cn/problem/CF149Dtag:搜索，记忆化搜索，区间DP思路：使用 f[l][r][i][j] 表示区间l和r之间l为i色，r为j色时的染色方案数。有两种情况，当 l 和 r 配对时，可以由 l + 1 到 r - 1更新过来。如果不配对，由 l 到 第一个配对的括号这段区间和由那个…

问题描述小R有nn部电脑，每部电脑的电池容量分别为aiai​。她可以使用两种不同的充电方式来给电脑充电：普通充电：每单位时间为电脑充电xx单位的电量。闪充：每单位时间为电脑充电4x4x单位的电量。现在，所有电脑的电量都为零。小R希望使用闪充给所有电脑充满电，计算她需要的总充电时间。请保留结果的小数点后两位。测试样例样例1：输入：n = 4 ,x =…

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分别表示都是浅层，都是深层和混合。当左边为浅层，右边为深层或者左边为混合…

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 ，所以只有当 …