RainAir
My OI Blog
RainAir
初级的动态规划

感觉自己 dp 非常的差,于是在这里集中整理一下。

这里都是非常初级的动态规划。

定义

何为动态规划? 大概上就是一个不断探索问题性质减少那些和答案有关的值的个数。

动态规划重要的三部曲:

  • 设计状态
  • 考虑转移
  • 考虑优化

由于这里是入门级别的动态规划,将不会考虑到优化。

背包问题

常见的背包问题

那我们来看一些题目吧。

BZOJ 2287

题目描述

ftiasch 有 $ N $ 个物品, 体积分别是 $W_1, W_2, \cdots , W_N $ 。 由于她的疏忽, 第 $ i $ 个物品丢失了。 要使用剩下的 $ N – 1 $ 物品装满容积为 $ x $ 的背包,有几种方法呢?– 这是经典的问题了。她把答案记为 $ Count(i, x) $  ,想要得到所有 $ 1 \leq i \leq N, 1 \leq x \leq M $ 的 $ Count(i, x) $  表格。

其中$ 1 \leq N \leq 2*10^3 $

$ 1 \leq M \leq 2*10^3 $

解题报告

这是一道经典的退背包问题。

我们设 $ f_i $ 表示填满容量为 $ i $ 的背包的方案数,状态转移方程显然是:

$$ f_i = f_{i-1} + f_{j-w_i}$$

然后按照题目意思,记 $ C_{i,x} $ 为不使用第 $ i $ 个物品填满容量为 $ x $ 的背包的方案数,状态转移方程显然是:

$$ C_{i,x} = \begin{cases} f_j – C_{i,x-w_j} & w_j \leq j \ f_j & w_j=j \ 1 & j=0\end{cases} $$

然后输出即可,时间复杂度 $ O(N^2) $

本质上是一个多项式除一个单项式。

参考代码

BZOJ 4033

题目描述

有一棵点数为 $ N $ 的树,树边有边权。给你一个在 $ [0,N] $ 之内的正整数 $ K $ ,你要在这棵树中选择 $ K $ 个点,将其染成黑色,并将其他的 $ N-K $ 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。

其中 $ N \leq 2000 $ .

解题报告

我们定义状态 $ f_{v,i} $ 为以 $ v $ 为根的子树中选取 $ i $ 个黑色节点对总答案贡献的最大价值。

这里的贡献如果按照题目定义,会特别难以计算,时间复杂度飙升。

所以我们自己定义边的贡献 $ val $ 为:边一侧的黑节点数*另一侧的黑节点数*边权+一侧的白节点数*另一侧的白节点数*边权 。

那么这个就变成了一个~~小清新~~背包问题。

我们可以列出转移方程为:

$$ f_{u,i} = max(f_{u,i},f_{u,i-j}+f_{v,j} + val) $$

其中枚举 $ v $ 为 $ u $ 的子节点, $ j $ 为在以 $ v $ 为根的子树中枚举选择的黑点。 $ val $ 为该条边的贡献。

$ val=j(k-j)w + (v_{size}-j)(N-K+j-size_v)w $

其中 $ w $ 为边的边权, $ v_{size} $ 为以 $ v $ 为根的子树的节点数量。

参考代码

总结

对于这种问题,找出题目中隐藏的容量和价值,巧妙转移问题,有时价值太难算可以自己选取一个正确好算的价值。

数位 dp

BZOJ1026

题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为 $ 2 $ 的正整数被称为windy数。 windy想知道,在 $ A $ 和 $ B $ 之间,包括 $ A $ 和 $ B $ ,总共有多少个windy数?

其中 $ 1 \leq A \leq B \leq 10^{18} $

解题报告

直接数位 dp。

设 $ f_{i,j} $ 表示考虑前 $ i $ 位,上一位是 $ i-1 $ 的方案数。

转移方程是
$$ f_{i,j} = f_{i,j} + f_{i-1,k}(j-k \geq 2) $$

直接计数统计即可。

参考代码

BZOJ1799

题目描述

给出 $ a,b $ ,求出 $ [a,b] $ 中各位数字之和能整除原数的数的个数.

其中 $ 1 \leq a \leq b \leq 10^{18} $

解题报告

我们设状态 $ f[i][j][k][0/1] $ 表示考虑前 $ i $ 位,数字和为 $ j $ ,数字和 $ mod\ m $ 为 $ k $ ,是否卡上界的情况下的方案数。

转移方程在代码里,就不写了。

参考代码

总结

对于数位 dp,主要是注意位与位之间的转换的公式推导和情况特判,细心。统计答案时对上下界和其他特殊情况的特判。这种问题较为简单,有规律可循。

状压 dp

BZOJ2560

题目描述

铭铭有 $ n $ 个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连接成一个整体。

现在已知所有珠子互不相同,用整数 $ 1 $ 到 $ n $ 编号。对于第 $ i $ 个珠子和第 $ j $ 个珠子,可以选择不用绳子连接,或者在 $ c_{i,j} $ 根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点,把绳子看作边,将所有珠子连成一个整体即为所有点构成一个连通图。特别地,珠子不能和自己连接。

铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大,因此只需输出答案对 $ 1000000007 $ 取模的结果。

其中 $ N \leq 15 $

解题报告

我们设状态 $ f_s $ 表示将状态 $ S $ 连通的方案。由于不容易直接算,我们考虑容斥原理。

设 $ g_s $ 表示所有子图的方案。

显然 $ g_s $ 可求。

对于 $ f_s $ 的计算可以由

$$ f_s = g_s – \sum_tf_t*g_{s-t} $$

计算得来。

参考代码

To Be Continue…

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/76
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

初级的动态规划
感觉自己 dp 非常的差,于是在这里集中整理一下。 这里都是非常初级的动态规划。 定义 何为动态规划? 大概上就是一个不断探索问题性质减少那些和答案有关的值的个数。 动态规划重…
扫描二维码继续阅读
2018-07-30
标签
近期评论