洛谷4516 [JSOI2018]潜入行动
LuoguLOJ分析容易想到一个 DP。设 $dp_{i,j,0/1,0/1}$ 表示以 $i$ 为根的子树，放了 $j$ 个监听设备，$i$ 有没有放监听设备，$i$ 有没有子节点放了监听设备，使得以 $i$ 为根的子树中除了 $i$ 的节点都被监听到的方案数。转移类似于树形背包，大力讨论一下即可。边界为 $dp_{u,0,0,0}=dp_{u,1,1,0}=1$，答案为 $dp_{1,k...
标签 动态规划 下的文章
- 首页
- 动态规划
洛谷5772 [JSOI2016]位运算
LuoguLOJBZOJ分析首先我们可以将 $n$ 个数互不相同且都小于 $R$ 的条件转化为 $R=A_0>A_1>A_2>\cdots>A_n$。考虑一个 DP。设 $dp_{i,S}$ 为前 $i$ 位大小状态为 $S$ 的方案数，其中 $S$ 的第 $i$ 位为 $0$ 表示 $A_i >A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时枚举...
洛谷5770 [JSOI2016]无界单词
LuoguLOJBZOJ分析容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $...
洛谷4044 [AHOI2014/JSOI2014]保龄球
LuoguLOJBZOJ分析太神了...看了好久才看懂...先考虑一些性质：如果上一轮是全中，那么一定放第一轮最小的补中（可以让第一轮最大的补中放在其它补中后），或者总分最大的失误。如果上一轮是补中，那么一定放第一轮最大的。可以发，我们要么取第一轮最小的补中，要么取第一轮最大的补中。考虑最优解大概是什么样子，可以发现是全中补中交替放，最后再放失误，而第一个失误要么是第一轮最大的，要么是总分最...
洛谷5774 [JSOI2016]病毒感染
LuoguLOJBZOJ分析首先那个条件的意思是如果往回走到了某个未被治愈的村庄，则必须治愈它。考虑 DP。设 $dp_{i}$ 表示前 $i$ 个村庄已经被治愈且此时在 $i$ 的最小死亡人数。转移枚举往回走到的位置，可以得到边界为 $w_{i,i}=s_n-s_i$。最后答案即为 $dp_n$。总时间复杂度 $\mathcal{O}(n^2)$。代码// ================...
洛谷4322 [JSOI2016]最佳团体
LuoguLOJBZOJ分析分数规划问题，考虑二分答案，推一推式子可以得到将 $p_i-mid\times s_i$ 作为价值，树形背包即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==========================...
洛谷4323 [JSOI2016]独特的树叶
LuoguLOJBZOJ分析先考虑一个 $\mathcal{O}(n^2)$ 的做法。先求出以每个节点为根，整棵树的哈希值。直接 DFS $n$ 次即可。然后，把 $A$ 的这 $n$ 个哈希值存到 map 中，然后枚举 $B$ 的每一个叶子节点，查一下删掉它后的哈希值是否在 map 中即可。这个算法的主要瓶颈在于求哈希值那一部分，考虑用换根 DP 优化这个过程。异或满足可减性，很容易抵消掉...
洛谷6082 [JSOI2015]salesman
LuoguBZOJ分析首先，一个点能停留 $s$ 次，等价于可以进入它的 $s-1$ 棵子树。先考虑第一问。 $dp_{i}$ 表示以 $i$ 为根的子树的最大收益，转移时在所有 $dp$ 值非负的子树选最大的那些进入即可。再考虑第二问。设 $f_i$ 表示以 $i$ 为根的子树中最大收益是否唯一。如果当前子树最大收益不唯一，那么有以下可能：一棵子树最大收益不唯一。选了一棵最大收益为 $0$...
BZOJ5038 [Jsoi2014]打兔子
BZOJ分析首先特判 $k\geq\left\lceil\frac{n}{2}\right\rceil$ 的情况，此时可以消灭所有兔子。但是上面的特判有一个例外：当 $n=3,k=2$ 时只能消灭两块菜地中的兔子，显然打最多的两块。考虑剩下的情况。容易发现，最优解中不会存在相邻的两块菜地都开过枪。考虑一个 DP：设 $dp_{i,j,0/1}$ 表示前 $i$ 块菜地，开了 $j$ 枪，当前...
BZOJ5031 [Jsoi2014]支线剧情2
BZOJ分析容易想到树形 DP。设 $f_u$ 为 $u$ 处有一个存档点，接下来不存档，访问完以 $u$ 为根的子树中所有剧情的最短时间。不难得到转移（这里的 $s_u$ 表示以 $u$ 为根的子树中叶子节点的个数）再设 $dp_u$ 为 $u$ 处有一个存档点，接下来可以存档，访问完以 $u$ 为根的子树中所有剧情的最短时间。$dp_u$ 的转移有些复杂。首先每个子节点 $v$ 可以不存...