「HDU6566」The Hanged Man
题意$n$ 个点的树 每个点有一个体积 $v_i$ 和收益 $w_i$。只能选择不相邻的物品 要求你输出 $\forall i \in [1,m]$，容量为 $i$ 的背包收益最大的方案数$n \leq 50,m \leq 5000$题解很 naive 的 dp 大概是 $f[i][j][0/1] $ 表示处理 $i$ 号点子树 已经用了 $j$ 容量，是否选择这个点的方案数 转移的时候搞个...
题意$n$ 个点的树 每个点有一个体积 $v_i$ 和收益 $w_i$。只能选择不相邻的物品 要求你输出 $\forall i \in [1,m]$，容量为 $i$ 的背包收益最大的方案数$n \leq 50,m \leq 5000$题解很 naive 的 dp 大概是 $f[i][j][0/1] $ 表示处理 $i$ 号点子树 已经用了 $j$ 容量，是否选择这个点的方案数 转移的时候搞个...
DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。 我们来找一道简单的题目入手：给定一棵树，点有点权，每次可以修改一个点的权值，每次修改后求这棵树的最大独...
题目链接题目描述给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作，要么修改一个点的点权，要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径，路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $.题解问的是所有可能路径上的最小点权的最小值，那我们来考虑一下路径的性质。 首先我们可以发现，如果将这个图分成几个点双联通分量的话，路径一定是经过了从 $s$...
题目链接题目描述给定一棵 $ N $ 个节点的树，需要维持以下个操作： 改变第 $ k $ 条边的边权； 改变点 $ u $ 到点 $ v $ 的边权为 $ w $； 将点 $ u $ 和点 $ v $ 路径上的边的边权都增加 $ w $； 询问点 $ u $ 和点 $ v $ 路径上的边权最大值。 其中 $ 1 \leq N \leq 10^5 $，操作+询问数目不超过 $ 10^5 $。