标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
洛谷5289 [十二省联考2019]皮配
LuoguLOJ分析首先注意到学校选择导师和选择派系是等价的。考虑 $k=0$ 的情况。则此时城市选择阵营与学校选择派系独立，可以分开处理。设 $f_{i,j}$ 表示前 $i$ 个城市有 $j$ 个人在蓝阵营的方案数，$g_{i,j}$ 表示前 $i$ 所学校有 $j$ 个人在鸭派系的方案数。转移即为 0/1 背包。最后卷积合并即可。考虑 $k\neq 0$ 的情况。注意到有限制的学校数很...
洛谷4383 [八省联考2018]林克卡特树
LuoguLOJ分析问题相当于选出恰好 $k+1$ 条点不相交的路径使得权值和最大，这里 $1$ 个点也算一条路径。先考虑一个朴素 DP。设 $dp_{i,j,0/1/2}$ 表示以 $i$ 为根的子树、选了 $j$ 条路径、$i$ 的度数为 $0/1/2$ 的最大权值和，转移讨论各种情况把子树合并进来即可。设 $f(k)$ 为选恰好 $k$ 条点不交路径时的最大权值和，通过打表或者感性理解...
洛谷4365 [九省联考2018]秘密袭击coat
LuoguLOJ分析首先把第 $k$ 大转化掉：不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都是 $x^n...
CF464D World of Darkraft - 2
CodeforcesLuogu分析显然装备之间没有区别，我们只要计算一种装备的期望，然后乘上 $k$ 即可。考虑倒推。设 $dp_{i,j}$ 表示剩余 $i$ 个怪物、装备等级为 $j$ 期望获得的金币数，转移有三种：选到了其它装备：概率为 $\frac{k-1}{k}$，期望收益为 $dp_{i-1,j}$。选到了等级为 $j+1$ 的当前装备：概率为 $\frac{1}{k(j+1)}...
洛谷2519 [HAOI2011]Problem A
Luogu分析每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。那么如果两个人的话不同且对应的区间无交，他们就可能都说了真话。把相同的区间缩在一起，问题变成每个区间有一个权值，选出若干个无交的区间使得权值和最大。这个可以直接 DP，把所有区间按右端点排序后，二分找到最后的左端点小于当前右端点的位置，然后转移即可。注意把 $a_i+1>n-b_i$ 的人掉，这些人一定说了...
洛谷5326 [ZJOI2019]开关
LuoguLOJ分析设 $P=\sum_{i=1}^n p_i$。设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。$F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有直接计算即可。代码// ==================================== // author...
AGC038E Gachapon
AtCoderLuogu分析我不喜欢容斥，我不喜欢组合意义，我不喜欢生成函数，我也没有精神首先 Min-Max 容斥一手转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去，转移要乘上一个 $-1$。算答案就把上面这个东西代回去就好了。代码// ==================================== // author: M_sea // websit...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
AGC035D Add and Remove
AtCoder分析可以发现题目中的贡献只有加，按照鸡贼的话来说这是一个很罕见的性质。倒着看整个过程，相当于每次往里面加一个数。我们考虑每个数对答案的贡献。假设当前有若干个数，第 $i$ 个数的贡献是 $x_i$，那么我们在 $i,i+1$ 中加一个数，新加的数的贡献显然是 $x_i+x_{i+1}$。这个 $i,i+1$ 对应原序列中的一段区间，因此可以 DP。设 $dp_{l,r,xl,x...