Yuhang's Blog

Category : Coding

单调队列DP优化

考虑状态转移方程： $$ f(i)= \min _ {L(i)\le j \le R(i)} \{g(j)\} + h(i) $$ 其中$i\le N$， $j \le M$。显然暴力... Read more

Coding

树上DP：换根法

更换树根会导致树的某个性质发生改变，而题目需要我们分别求出以每一点为根时，对应的性质的值。 Read more

Coding

Luogu P1272：树形背包

树上, 状态必然有一个维度是“子树的根节点编号”, 记作$u$. 需要完全理解题意, 可构造出本题用$f(u,j)$来表示“将以$u$为根节点的子树拆成一棵大小是$j$的子树至少需要切断多少条边... Read more

Coding

插头DP

看了很多插头DP的教程，感觉都说的不是很清楚。但我还是搞明白了它是什么。 Read more

Coding

题解 CF55D ：数位DP+数论

这题做了半天。美丽的数的定义是“可以被自己的所有非零数位整除的数”。做数位DP，想的就是每个状态需要什么参量来表示。注意到这个定义的限制并不在选取每个数位的时候，而是... Read more

Coding

数位DP

问题类型是求解小于等于某个给定$n$的、数位符合一定条件的的正整数的个数。注意如果题目要求是求解某个正整数区间上的、符合一定条件的数的个数，则可以轻易化归到上述问题。 Read more

Coding