动态规划

显然直接 $01$ 背包会超时并且超空间 套路：分层 $DP$ 「考虑将每个子结构看作一层（也就是包含了不止 $1$ 个物品的信息），并且大层不会对小层造成影响，可以考虑先进行每一层的自我更新（即用当前层物品更新当前层答案），再进行层的合并，此时考虑低层对高层的影响」 正题 那么这题有一个特殊性质： $V_i = a \times 2^b$ b值大的物品不会影响零碎剩余的重量上限。 将物品按b值分阶段处理。 那么就是分层 $DP$ 先通过普通的 $01$ 背包更新当前层自身最优解 再进行层合并： 令 $g_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$ 的最优解，$f_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$，并且再加上 $V_{total}​$ 的 $1…i - 1​$ 位的最优解 那么对于第 $i$ 层，枚举当前 $j$ 对于转移，枚举在自身层内消耗的空间 $(j - k) \times 2^i$，那么还剩下 $k \times 2^i + V_{total}\{1…i - 1\}$ 的空间，分配给上一层，那么可得转移方程为 （注：$w_i ...

题意给定 $n$ 个线段，每个线段有一个权值 $w_i$，每次取轴上一点，获得的权值为选择的覆盖在当前点上的线段的最大权值，求最终覆盖所有线段后需要的最小权值 题解好吧是一道非常水的区间 $dp$ 然而我并没有想出来所以我是真的绝望 先把 $l_i, r_i$ 离散化后令 $f_{l, r}$ 表示完全覆盖区间 $[l, r]$ 的线段的最小权值，设完全处于 $[l, r]$ 的线段中权值取最大值的线段 $p$，则有转移方程$$f_{l, r} = \min \{f_{l, k - 1} + f_{k + 1, r} + w_p\} (l_p \le k \le r_p)$$所以注意一定要完全覆盖，$[l, k - 1], [k + 1, r]$ 才不会对 $[l, r]$ 造成影响，于是我就卡这儿了 谨以此文纪念我逝去的智商 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 ...

首先因为点数不多，可以考虑先在 $4r \times c$ 时间内将每个点朝每个方向可以到达的位置预处理出来，建成图 那么现在容易看出是斯坦那树问题，所以考虑将问题简化一下： 现在给定 $n$ 个不同级别的机器人，将两段级别的机器人合并需要花费 $c_i$，那么将所有机器人合并的最小花费是多少 这个问题显然使用区间 $DP$ 可以解决，那么扩展到斯坦那树上即可 令 $f[l][r][i]$ 表示区间 $l, r$ 的机器人合并后位于位置 $i$ 的最小花费，则有$$f[l][r][i] = \min \{f[l][k][i] + f[k + 1][r][i]\}$$以及$$f[l][r][i] = \min\limits_{p link to i} \{f[l][r][p] + 1\}$$第二个式子直接 $SPFA$ 会超时 但是观察每条边的贡献都为 $1$，所以可以将 $SPFA$ 优化成 $BFS$ 的复杂度 类似堆优化的思想，开两个队列，一个存初始的经过 $f$ 排序的点，一个存被松弛的点，由于边的性质及 $que1$ 经过排序的原因，所以 $que2$ 一定也是按 $ ...

题目描述$01$ 背包，数据范围 $1 \le n \le 1e06, 1 \le weight_i \le 300$ 题解神仙 $01$ 背包 考虑重量较小，故可以考虑根据重量分层处理 令 $f_{i, j}$ 表示使用前 $i$ 个重量，总共花费 $j$ 容量的最大价值 容易注意到在同一重量中显然要优先选择价值大的，故将每种重量按价值排序，令 $sumv_{i, j}$ 表示重量为 $i$ 的前 $j$ 大的价值前缀和，则有$$f_{i, j} = \max\limits_k \{f_{i - 1, j - ki} + sumv_{i, k}\}$$然后（通过看题解）可以发现，因为是 $j - ki$，故可以考虑按照 $j \mod i$ 分类处理，这样是满足决策单调性的 至于证明，为了方便可以将式子简化成 $f_i = \max \{f_j +sumv_{i - j}\}$ 的形式，然后用反证法或是四边形不等式都容易证明 那么最后就可以用决策单调性的套路代码或者是用分治解决了 分治比较简单，大概就是看在处理区间 $[u, v]$， $[l, r]$ 决策区间内对于 $mid$ 位 ...

Solution Ⅰ一道有点有趣的树形 $dp$ + 容斥，反正绕了我半天，这么神仙我也不可能写出来 首先考虑基本思路，直接求解恰好 $k$ 个较难，故考虑先求解大于等于 $k$ 的相似度的方案数，然后再容斥 考虑选定了必选的若干条边后计算方案数。显然此时整个图被分成了若干连通块，假设有 $k$ 个连通块，将连通块缩点，考虑它们可以组成的树的方案数，本来应该是 $k^{k - 2}$，然而对于每个连通块的缩点，它可以向其它连通块中包含的任意一点连接，也就是说，在 purfer 序列中，应当考虑连通块内的点编号在序列中的出现情况，而不是仅仅考虑连通块编号出现在序列中，故 prufer 序列中的每个位置可以填 $n$ 个数，即 $n^{k - 2}$，然而考虑了父亲，还需要考虑儿子，作为叶子节点的缩点后的连通块，同样的里面也是任意点向外连边，故还需乘上 $\prod size_i$，其中，$size_i$ 为连通块 $i$ 的大小，那么综上，对于一个存在 $k$ 个连通块的图，其构造的生成树的方案数为 $n^{k - 2} \times \prod size_i$ 那么现在考虑求解 $\p ...