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 …

url: https://www.luogu.com.cn/problem/P3047tag:树形DP, USACO, 2012思路：用f[u,m] 表示以u为根节点，向下走出不超过m步时的权值，d[u, m] 表示以u为根节点，向上或向下走不超过m步时的权值。利用两次dfs分别求出f和d，最后输出每个节点作为根节点时的权值和即可。代码：#incl…

url: https://www.luogu.com.cn/problem/P1944思路：用动态规划的思路来做。用f[i]表示以s[i]结尾的括号匹配字符串，属性是最大值。从第二个字符开始检查，如果当前字符为 ）或 ] ，以及距离上一个匹配好的字符串前的一个字符与其相匹配，则更新长度为f[i] = f[i - 1] + 2，同时可以检查前两个字符…

url: https://www.luogu.com.cn/problem/P1074tag:NOIP2009 提高组，搜索，剪枝，位运算，NOIP提高组，2009思路：核心变量解析a[10][10]：存储数独棋盘，ai表示第i行第j格的数字（0表示空格）r[10]：行约束，r[i]的二进制第k位表示第i行能否填数字k+1（1表示可用）c[10]：…

url: https://www.luogu.com.cn/problem/P2476tag:SCOI2008，动态规划，搜索，记忆化搜索思路：开一个6维的数组来表示状态（因为每种情况有多种，所以不能用压位bit），分别表示足够涂1， 2， 3， 4， 5块木头的颜色有几种，最后一维表示上一种颜色的种类。然后用记忆化搜索来做。参考： https:/…

url: https://www.luogu.com.cn/problem/P1278tag:记忆化搜索，状压DP思路：记忆化搜索，dfs两个参数一个是当前的字母，另外一个是当前的状态。f[x, y] 表示当以字符串x开头是状态为y时最大的字符串长度。代码：#include <iostream> #include <vector&…

url: https://www.luogu.com.cn/problem/P2966tag:USACO09DEC，最短路，排序，USACO，2009思路：多次询问，点的数据范围小，所以可以用floyd，如果没有点权，那么这道题就是经典的多源汇最短路。为了处理这个点权，我们可以将每一个节点按照点权的大小从小到大排序，然后对于每一个中间节点都是按照从…