昨天将一些没有用的可以卖的vps卖了。今天将原来放在旧主机上的一个服务迁移到了现在的服务器上面。racknerd上面的服务器我估计不好出，就到时候不续费就好。现在相当于将每年的服务器成本降低了，太好了。

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

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最后得出…