Tag: dp

22 篇文章

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…