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

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

url: https://www.luogu.com.cn/problem/P1433tag: 动态规划，状压DP，dfs，记忆化搜索思路：可以是状态压缩dp，也可以是用dfs加上记忆化搜索。这里就用dfs加上记忆化搜索。用二进制来存储每一种状态，每次访问一个点就将那个点异或一下。最后每次都是返回一个答案。dp中存的是从x点开始走走到最后一个点的最…

url: https://www.luogu.com.cn/problem/P2672tag:NOIP2015 普及组，贪心，线段树，树状数组，前缀和，动态规划。思路：思路都是用贪心的策略，有两种情况，一种是取前x个a最大的客户，第二种是取前x - 1个a最大的客户，然后再从第i到n个中选择距离最远的一个去替换第x个a最大的客户，两种情况取最大值输…

url: https://www.luogu.com.cn/problem/P1108tag:动态规划思路：问题1就是求最长下降子序列。问题2可以用c[i] 来表示以i为结尾长度为f[i] 的所有下降子序列，然后属性是数量。他可以由倒数第二个数的情况来转移，初始化是当长度为1时数量为1，之后遍历j从1到i，如果满足长度比f[j]大1，然后d[j] …

url: https://www.luogu.com.cn/problem/P3135tag:枚举，构造，动态规划思路：看了题解好像是可以用动态规划中的求最大子矩阵来做，但是这里用了很暴力的写法，加上前缀和优化也能过。这个做法本质上就是不断地枚举每一个矩形然后判断四条边是不是满足条件，然后再更新最大值就好了。代码：#include <iost…

url: https://www.luogu.com.cn/problem/P1115tag：最大子数列，Kadane 算法，动态规划思路：使用动态规划得方法来求解，用两个变量currentSum，和maxSum，分别来维护以当前位置结尾的最大子段和以及全局的最大子段和。状态转移分别是currentSum = max(a, currentSum +…