标签: dp

24 篇文章

LuoguP2605 [ZJOI2010]基站选址 题解
Description 题目链接 有 $N$ 个村庄坐落在一条直线上,第 $i(i>1)$ 个村庄距离第 $1$ 个村庄的距离为 $D_i$。需要在这些村庄中建立不超过 $K$ 个通讯基站,在第 $i$ 个村庄建立基站的费用为 $C_i$。如果在距离第 $i$ 个村庄不超过 $S_i$ 的范围内建立了一个通讯基站,那么村庄就被通讯信号覆盖。如果第 …
Luogu P3237 [HNOI2014]米特运输 题解
Description 题目链接 又臭又长的题面差评 给定一棵树,该树满足一定的性质: 节点 $x$ 的所有子节点权值必须相等节点 $x$ 的所有子节点的权值之和等于 $x$ 的权值 Solution 设第 $x$ 个节点的权值为 $v$,它有 $sz[x]$ 个直系子节点,显然,这 $sz[x]$ 个直系子节点的权值均为 $\frac{v}{sz…
Luogu P1896 [SCOI2005]互不侵犯 题解
Describe 题目链接 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 注:数据有加强(2018/4/25) 1 <=N <=9, 0 <= K <= N * N Solution 状压DP。 判断两个国王是否相互干扰…
Luogu P3174 [HAOI2009]毛毛虫 题解
Describe 题目链接 对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树(图 $1$)抽出一部分就变成了右边的一个毛毛虫了(图 $2$)。 Solution 毛毛虫? 很明显,我们可以先预处理出每个点的入度。 显然最后的答案就是$\sum{a_i}-(s-1…