CF115E Linear Kingdom Races
CodeforcesLuogu分析考虑 DP。设 $dp_i$ 表示前 $i$ 条道路的最大收益，不难得到转移这里的 $c(i,j)$ 表示修建 $i$ 到 $j$ 的道路的花费，$w(i,j)$ 表示修建 $i$ 到 $j$ 的道路获得的收益。考虑用线段树优化，即要求扫到 $i$ 时每个叶结点的值 $j$ 为 $dp_j-c(j+1,i)+w(j+1,i)$。对于一个新的 $i$，将 $[...
标签 动态规划 下的文章
- 首页
- 动态规划
洛谷4516 [JSOI2018]潜入行动
LuoguLOJ分析设 $dp_{i,j,0/1,0/1}$ 表示以 $i$ 为根的子树，已经放了 $j$ 个监听设备，$i$ 是否放了监听设备，$i$ 是否被子树中的点监听时子树中除 $i$ 外的所有点都被监听的方案数。转移类似于树形背包，需要将各种情况讨论清楚。边界为 $dp_{i,0,0,0}=dp_{i,1,1,0}=1$。代码// =========================...
洛谷5772 [JSOI2016]位运算
Luogu分析先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直接枚举...
洛谷4044 [AHOI2014/JSOI2014]保龄球
Luogu分析太神了...看了好久才看懂...先考虑一些性质：如果上一轮是全中，那么一定放第一轮最小的补中（可以让第一轮最大的补中放在其它补中后），或者总分最大的失误。如果上一轮是补中，那么一定放第一轮最大的。可以发，我们要么取第一轮最小的补中，要么取第一轮最大的补中。考虑最优解大概是什么样子，可以发现是全中补中交替放，最后再放失误，而第一个失误要么是第一轮最大的，要么是总分最大的。但是由于...
洛谷5774 [JSOI2016]病毒感染
Luogu分析首先那个规定的意思是如果往左走就要把左边所有没治愈的村庄治愈。可以发现整个过程可以划分成若干段，每段以任意顺序治愈后回到该段的起点，再治愈下一段。考虑 DP。设 $dp_i$ 表示治愈前 $i$ 个村庄的最小死亡人数。记 $s$ 为 $a$ 的前缀和，$w_{i,j}$ 为从 $i$ 出发治愈 $[i,j]$ 中所有村庄再回到 $i$ 的最小死亡人数，容易得到转移边界为 $w_...
洛谷5770 [JSOI2016]无界单词
Luogu分析容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$，如果 $...
洛谷4323 [JSOI2016]独特的树叶
Luogu分析先考虑一个 $\mathcal{O}(n^2)$ 的做法。先求出以每个节点为根，整棵树的哈希值。然后，把 $A$ 的所有 $n$ 个哈希值丢到一个 map 里去，然后枚举 $B$ 的每一个叶子节点，判断删掉后的哈希值是否在 map 中即可。这个算法的主要瓶颈在于 $\mathcal{O}(n^2)$ 求哈希值，我们考虑优化这个过程。异或满足可减性，很容易抵消掉。所以我们设哈希函...
洛谷4322 [JSOI2016]最佳团体
Luogu分析二分答案 $mid$。考虑 check()。将 $p_i-mid\times s_i$ 作为价值跑树形背包即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==================================...
洛谷6096 [JSOI2015]地铁线路
Luogu分析第一问考虑最短路。对于每条线路建一个点，线路上的站向线路连边权为 $1$ 的边，线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。假设一条线路的 $dis$ 为 $d$，则我们可能在 $dis$ 为 $d-1$ 的站上车，在 $dis$ 为 $d$ 的站...
洛谷6082 [JSOI2015]salesman
Luogu分析首先，一个点能停留 $s$ 次，等价于可以进入它的 $s-1$ 棵子树。先考虑第一问。 $dp_{i}$ 表示以 $i$ 为根的子树的最大收益，转移时在所有 $dp$ 值非负的子树选最大的那些进入即可。再考虑第二问。设 $f_i$ 表示以 $i$ 为根的子树中最大收益是否唯一。如果当前子树最大收益不唯一，那么有以下可能：一棵子树最大收益不唯一。选了一棵最大收益为 $0$ 的子树...