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

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/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/P1282tag:动态规划，枚举，背包DP思路：用 f[i][j] 表示用前i块多米诺骨牌形成的差值为j时旋转次数。因为差值的范围是-5000-5000，所以数组加一个5000的偏移量。状态转移方程为 f[i][j + p] = min(f[i - 1][j - (a[i]…

url: https://www.luogu.com.cn/problem/P5322tag:动态规划，背包DP思路：读入的时候反着读，用 a[i][j] 来表示第i座城第j个人出的兵。然后对每座城中的s种出兵的方式排序，得到 a[i][j] 表示第i座城前j个出兵最多的人出的兵。然后用分组背包的方式，每一座城每种出兵数量，用那座城的每一个前k个玩…

url: https://www.luogu.com.cn/problem/P1156tag:动态规划，排序，背包DP思路：对于每一个垃圾来说，为了不去处理时间，可以按照时间顺序排列，之后只要关注两个属性，一个是高度，一个是时间。定义 f 数组，表示当前高度下生存的时间。每次更新先是判断当前高度能否等到这个垃圾，然后判断如果堆起来能不能逃出去，能的…

url: https://www.luogu.com.cn/problem/P2340tag:动态规划，背包，USACO， 2003思路：可以转化为01背包问题来做，因为每个奶牛都只有选和不选两种状态。对于背包问题，需要考虑三个属性，一个是背包容量，一个是体积，还有一个是价值。在这道题中，iq和eq是等价的属性，所以可以一个当作体积，另外一个当作价…

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] …