解题营_动规

动态规划
- 前言
- 题目

动态规划

前言

8.20

写过去的时间比较久了也懒得补代码了思路问题不是很大扔下了...

大多数的题已经做完了代码其实是有的但是隔得时间比较久了再回来写就感觉写不下去了.

再找机会吧

当然做过的题目在洛谷上都是可以找到提交记录的..

题目

P2704 炮兵阵地

经典的状压 (dp)

P5933 串珠子

状压

联通难以处理正难则反考虑算出不联通的方案数再用总方案数减去

设 (f_S) 表示选点状态为 (S) 时有多少联通子图

联通子图的数量不容易计算考虑计算不联通的子图数量

随便钦定 (S) 内的一个点 (p) 枚举 (p) 所在的联通块 (T in S) 预处理 (g_S) 表示 (S) 内的子图数量(所有边的乘积)

P1777 帮助

将移动 (k) 分为两步先删再插入被删的数

如果已知删去的是那些数插入的时候可以贪

一个数在插入过程中产生代价当且仅当该数在删除过程中删干净了

数的种类可以压

仅考虑删除设 (f_{i, j, x}) 表示仅考虑前 (i) 个数从中删掉 (j) 个数且最后剩下的数是 (x) 的最小混乱度

考虑插入步骤产生的影响直接压没被删掉的数的集合设 (f_{i, j, x, S}) 表示考虑前 (i) 个数删去 (j) 个数最后剩下的数为 (x) 且未被删除的数的集合为 (S) 时的最小混乱度

P6622 信号传递

从第 (i) 个位置传到第 (j) 个位置如果 (i < j) 则时间为 (j - i) 否则为 (K imes (i + j))

信号站的数量少可以压

信号传递的顺序无关紧要只序言知道对于每个 (i, j) 有多少次从 (i) 传到 (j) 和有多少次从 (j) 传到 (i)

预处理每两个信号站之间的传递次数

对于位置 (x, y) 的两个信号站如果有 (A) 次从左到右和 (B) 次从右到左那么产生的时间为 (A(y - x) + BK(x + y))

设 (f_S) 表示给 (S) 内的信号站排序的最小传递时间每加入一个点算它作为 (x) 和 (y) 的时间贡献

P3959 宝藏

点数少压点集枚举子集

最后打通的为一棵树

代价和点到根的距离有关考虑距离

按照离根的距离一层一层加点

设 (f_{i, S}) 表示打通 (S) 这个集合距离根最远的点为 (i) 的最小代价转移枚举距离为 (i) 的子集 (T) 然后对于 (T) 中每个点在 (S/T) 里找到代价最小的点

Pay to Win

通过以下操作将 (0) 变成 (N)

花 (A) 将数字乘 (2)

花 (B) 将数字乘 (3)

花 (C) 将数字乘 (5)

花 (D) 将数字加一或减一

(N leq 10^{18})

设 (f_x) 表示将 (0) 变为 (x) 的最小代价

第一个乘法前可能有若干个加一

将一次乘法和若干次加法绑定成一次操作

复杂度为 (O(N))

可以采用记搜避开转移不到 (N) 的状态有用的 (x) 只有 (frac N{2^a3^b5^c}) 的上取整或下取整形式

P3174 毛毛虫

确定一条链就能确定一个对应的毛毛虫相当于求链

一条链可以断成两段设 (f_u) 表示以 (u) 为根的子树中以 (u) 为端点的链能抽出的毛毛虫的最大值维护最大和次大儿子

P1472 奶牛家谱

恰好为 (K) 比较麻烦改为不超过 (K)

设 (f_{i, j}) 表示有多少点数为 (i) 最大深度不超过 (j) 的二叉树转移枚举左儿子的点数

P1131 时态同步

对每个节点其包含的所有叶子到它的距离相同

设 (f_u) 表示将 (u) 为根的字数内时态同步的最小代价

转移找最大的到叶子的距离其他儿子与该距离做差

P1623 树的匹配

设 (f_{u, 0/1}) 表示 (u) 为根的子树内的 (u) 点是否选的最大匹配数量

[f_{u, 0} = sum max(f_{v, 0}, f_{v, 1})\ d = f_{v, 0} - max(f_{v, 0}, f_{v, 1})\ d = min(0, f_{v, 0} - f_{v, 1})\ f_{u, 1} = f_{u, 0} + 1 + d ]

设 (f_{u, 0/1}) 表示 (u) 为根的子树内 (u) 点是否选的匹配数匹配方案数

[f_{u, 0} = prod (f_{v, 0} + f_{v, 1})\ f_{u, 1} = f_{u, 0}sum frac{f_{v, 0}}{f_{v, 0} + f_{v, 1}} ]

设 (g_{u, 0/1}) 表示 (u) 为根的子树内最大匹配

设 (f_{u, 0/1}) 表示 (u) 为根的子树内 (u) 点是否选的最大匹配的方案数

[f_{u, 0} = prod ([g_{v, 0} geq g_{v, 1}] f_{v, 0} + [g_{v, 0} leq g_{v, 1}]f_{v, 1})\ f_{u, 1} = f_{u, 0} imes sum_{d_v = d} frac {f_{v, 0}}{[g_{v, 0} geq g_{v, 1}] f_{v, 0} + [g_{v, 0} leq g_{v, 1}]f_{v, 1}} ]

通过 (g) 判断转移是否可行

P5322 排兵布阵

要么直接占下来要么不派

设 (f_{i, j}) 表示在前 (i) 个城堡派遣 (j) 个士兵的最大得分转移枚举第 (i) 个城堡派遣的士兵数量(其他玩家派的兵力乘 (2) 加 (1))

P4141 消失之物

容斥或者卷

P1272 重建道路

树上背包

小 (Y) 的背包计数问题

设 (f_{i, j}) 表示使用前 (i) 个物品装满体积和为 (j) 的背包的方案数

转移枚举第 (i) 个数用了多少个

[f_{i, j} = sum_{k = 0}^i f_{i - 1, j - i imes k} ]

复杂度 (O(n^3))

一般的多重背包

二进制拆分 (O(n^2log n))

对于方案数

单调队列 (O(n^2))

前缀和优化

预处理 (g_{i, j})

[g_{i, j} = sum_{k = 0}^{lfloor frac ji floor} f_{i, j - ki} ]

转移

[f_{i, j} = g_{i - 1, j} - g_{i - 1, j - i imes (i - 1)} ]

P3216 数学作业

设 (f_i) 表示将 (1) 到 (i) 拼起来如果 (i) 的位数为 (k) 则转移为 (f_i = f_{i - 1} imes 10^k + i)

对于 (k) 相同的一段数可以用矩阵快速幂优化 ({f_i, f_{i + 1}, i})

P2579 沼泽鳄鱼

若没有食人鱼设 (f_u) 表示走到 (u) 点的方案数 (g_u) 是多走一步到达 (u) 点的方案数有 (g = f imes A) 其中 (A) 为原图的邻接矩阵所以走 (K) 步就是求 (A^K)

考虑食人鱼的话可以将食人鱼的周期直接看做 (12) 设当前食人鱼在周期中走到 (i) 有 (g = f imes A imes B_i) 其中 (B_i) 只在对角线上没有食人鱼的点上有值

于是要求的矩阵变为 (AB_1AB_2AB_3dots AB_{K mod 12 + 1}) 将每十二个绑到一起做矩阵快速幂剩下的直接乘上去

P3205 合唱队

每个人只能插入到最左边或最右边不能插入到中间

在插入的过程中队形始终对应最终队形的一个区间

区间 (dp)

设 (f_{l, r, 0/1}) 表示排列成区间 ([l, r]) 的序列最后一个数插入左边还是右边的方案转移枚举倒数第二个人插入左边还是右边

P4302 字符串折叠

区间 (dp)

设 (f_{l, r}) 表示将 ([l, r]) 折叠的最小长度

转移考虑两种情况

多个折叠构成枚举分解点分成两个

本身就是一个折叠该串由若干小串重复若干次得到

枚举小串的长度小串的长度必须整除原串的长度确定小串长度后再暴力判断原串是否由小串重复得到

AT2558 Many Moves

设 (f_{i, j}) 表示处理前 (i) 个要求后两个棋子的位置分别在 (x_i) 和 (j)

[f_{i + 1, j} = f_{i, j} + |x_i - x_{i + 1}|\ f_{i + 1, x_i} = f_{i, j} + |j - x_{i + 1}| ]

复杂度 (O(qn))

以线段树分别维护 (f_{i, j}, f_{i, j} + j, f_{i, j} - j) 的第二个维度

将 (i) 看做时间轴以 (j) 为下标随着 (i) 的改变维护线段树

对于上面第一个式子相当于全局加

第二个式子 (min (f_{i + 1, x_i}, f_{i, j} + |j - x_{i + 1}|))

分类讨论拆绝对值

对 (j leq x_{i + 1}) 求 (min (f_{i, j} + x_{i + 1} - j))

对 (j > x_{i + 1}) 求 (min (f_{i, j} + j - x_{i + 1}))

(x_{i + 1}) 是固定的可以拿出来

线段树中维护 (f_{i, j} + j) 和 (f_{i, j} - j)

P1850 换教室

设 (f_{i, j, 0/1}) 表示前 (i) 个教室申请其中 (j) 个最后一个是否申请的最小期望代价

转移枚举上一个教室是否申请

CF908D New Year and Arbitrary Arrangement

无穷等比数列求和当 (0 < q < 1)

[sum_{i = 1}^{infty} q^i = frac 1{1 - q} ]

在最后加一个 (a) 没有影响在最后加一个 (b) 会增加若干个 (ab) 序列

设 (f_{i, j}) 表示当前有 (i) 个 (a) 和 (j) 个 (ab) 子序列的状态加到最后期望 (ab) 子序列的数量是多少

[f_{i, j} = A imes f_{i + 1, j} + B imes f_{i, j + i} ]

当 (j geq k) 时

[f_{i, j} = j ]

第一维没有边界

将 (i) 限制在 (k) 以内考虑如果直接求 (f_{k, j}) 的值

第二维会超过 (k) 直接带入值

[f_{k, j} = Af_{k + 1, j} + B(j + k)\ = A^2f_{k + 2, j} + AB(j + k + 1) + B(j + k)\ = dots\ = sum_{i = 0}^{infty}A^iB(j + k + i)\ = sum_{i = 0}^{infty}A^iB(j + k) + sum_{i = 0}^{infty}A^iBi\ = B(j + k)sum_{i = 0}^{infty}A^i + Bsum_{i = 1}^{infty}A^ii ]

对于前面那一坨东西有:

[B(j + k)sum_{i = 0}^{infty}A^i = frac {B(j + k)}{1 - A} = j + k ]

对于后面那一坨东西

设:

[sum_{i = 1}^{infty}A^ii = Q ]

有:

[Q - AQ = A + sum_{i = 2}^{infty}A^i = sum_{i = 1}^{infty}A^i = frac A{1 - A} ]

所以:

[Q = frac A{(1 - A)^2} = frac A{B^2} ]

故原式可化为:

[j + k + frac AB ]

得到了 (f_{k, j}) 的值

所以

当 (i = k) 时 (f_{i, j} = i + j + frac AB)

当 (j geq k) 时 (f_{i, j} = j)

复杂度 (O(k^2))

答案为 (f_{0, 0})

CF713C Sonya and Problem Wihtout a Legend

设 (b_i = a_i - i)

则 (a_i leq a_{i + 1} - 1) 等价于 (b_i leq b_{i + 1})

设 (f_{i, j}) 表示将前 (i) 个数变为单调不减且 (b_i = j) 的操作数

[f_{i, j} = |b_i - j| + min_{k leq j}(f_{i - 1, k}) ]

后面那一坨东西是前缀最小值可以预处理

[g_{i, j} = min(f_{i, j}, g_{i, j - 1})\ f_{i, j} = |b_i - j| + g_{i - 1, j} ]

复杂度与值域有关离散化

P2511 木棍分割

第一问显然可以二分第二问 (dp)

设 (f_{i, j}) 表示前 (i) 个数分为 (j) 段每段不超过 (x) 的方案数

转移枚举最后一段的长度

[f_{i, j} = sum_{k = 1}^i f_{i - k, j - 1}[sum_{i - k + 1, i} leq x] ]

复杂度 (O(mn^2)) 显然可以超时

(k) 的枚举是有边界的将 (dp) 数组的第一维可以前缀和优化

边界也就是以每一个位置作为右端点的最大区间是可以二分或者双指针找到边界后可以把后面那东西去掉

P5999 kangaroo

相当于求有多少排列大小交替并且第一个和最后一个分别为 (s) 和 (t)

对于一个合法的排列 (p) 如果只考虑不超过 (x) 的值 (p) 会被划分为若干连续段

设 (f_{i, j}) 表示考虑不超过 (i) 的值有多少最终排列能被划分为恰好 (j) 段的方案数

转移考虑加入 (i) 后 (i) 是单独作为一个段或是将两个相邻的段连接成了一个段

由于 (i) 是当前最大值所以 (i) 不会作为段的端点

[f_{i, j} = f_{i - 1, j + 1} imes j + f_{i - 1, j - 1} imes (j - [i > s] - [i > t])\ f_{s, j} = f_{s - 1, j} + f_{s - 1, j - 1}\ f_{t, j} = f_{t - 1, j} + f_{t - 1, j - 1} ]

答案为 (f_{n, 1})

P6280 Exercise G

对于每个位置建图的话会形成若干个环所以 (K) 就是所有环长的 (lcm)

(lcm) 只需要考虑每个质数的指数

相当于求所有 (K) 的和满足 (K) 质因数分解后所有的 (p^x) 加起来不超过 (n)

设 (f_{i, j}) 表示前 (i) 个质数所有 (p^x) 加起来为 (j) 时 (K) 的和

[f_{i, j} = f_{i - 1, j} + sum_{x > =}f_{i - 1, j - p^x} imes p^x ]

CF348D Turtles

可以看做一只从 ((1, 2)) 到 ((n - 1, m)) 另一条从 ((2, 1)) 到 ((n, m - 1)) 不妨设为 (A, B, C, D)

两只乌龟可以分别 (dp) 再合并考虑如果剔除相交的方案

对于 (A o B, C o D) 的任意一条相交路径都可以在第一个交点位置翻折得到 (A o D, C o B) 的路径这两者是一一对应的关系所以方案数相同

做两次 (dp) 再相乘即 ((A o B) imes (C o D) - (C o B) imes (A o D))

P1453 城市环路

基环树独立集

设 (f_{u, 0/1}) 表示 (u) 为根的子树中最大独立集

找一条边断掉跑树形 (dp) 即可