QBXT Jinan Day5

Posted on | In , | | Visitors:
Words count in article: 4.9k | Reading time ≈ 18


Day5 上午——动态规划

大纲

DP的类型

序列DP
数位DP
概率DP
树形DP
状态压缩DP
DP套DP

DP的优化

形式优化
决策单调性优化
斜率优化
凸单调性DP优化

例题、[HAOI2011]problem a

题面见P2519

思路

将问题转化一下，一个人说的话如果为真说明从第$a_i+1$到第$n-b_i$个人的分数是一样的.
如果我们把这样一个模型看成一条线段，那么在这$n$条线段中，相交且互不重合的线段一定不能同时为真话，所以问题就转化为选出尽可能多的不相交或完全重合的线段，且对于某条线段完全重合的个数要小于等于线段长。
所以做法就很明显了，先求出说最多的说真话的人数，用总人数去剪。具体做法为：将每个人对应的线段放在一起进行双关键字排序，合并完全包含的线段，每一个线段上存一个权值$V_i$，现在就是要从$m$个线段中取出不相交的线段使得权值和最大，这就可以DP了。
将所有线段按右端点排序，设$f_i$为到第$i$个线段的最优解。
转移的时候先二分$[1,i)$之间满足$R_k<L_i$的$f_k$最大的$k$，转移方程为$f_i=\max(f_{i-1},f_k+V_i)$
最终答案为$n-f_m$

一、数位DP

数位DP常用来统计或查找一个区间满足条件的数，然后按数位顺序DP，一般需要仔细分情况讨论，常见处理如将区间拆为$[1, R], [1, L)$，记忆化，预处理等。

例题一、[SDOI2013]淘金

题面见P3303

思路

考虑对于一个$i$，有多少$j$满足$f_j=i$，记为$v_i$
不难发现，$[1,n]$内的任何数各位相乘的结果最多只有4个质因子$2 ,3 ,5 ,7$，也就是说$i$可以被分解为$2^a\times 3^b\times5^c\times7^d$，这样的$i$在$n\le10^{12}$范围内其实是很少的这个个数设为$m$。
所以我们可以设计状态$f_{i,j,0/1}$表示从低位到高位的第$i$位，各位的乘积为$j$（离散化后），最后一维表示是否小于等于$N$
转移的时候枚举第$k$位，如果$k|j$
那么$dp_{i,j,0/1}$可以从$dp_{i-1,\dfrac{j}{k},0/1}$转移过来
最终我们是要求位置$(x,y)$的价值$v_x\times v_y$的前$K$大之和。
考虑将$v$从小到大排序，用大根堆维护$m$个指针$p_i$，分别表示的是$v_1$到$v_m$，维护堆的关键字为$v_{p_i}\times v_i$，贪心选择$K$个求和得到答案。

二、概率和期望DP

概率DP是一类求事件概率或期望的DP的总称。对于求概率问题，有时利用补集转化，或者将其转化为计数问题；而对于求期望则大多利用期望的线性性来解决问题。

贝叶斯公式

条件概率$P(y|x)$
联合概率$P(y,x)$
$P(x,y)=P(x,y)=P(y|x)P(x)=P(x)P(y)$
$P(x,y)=P(x|y)P(y)$
贝叶斯公式：$P(y|x)=\dfrac{P(x|y)P(y)}{P(x)}$

例题一、亚瑟王

给你$N$张牌，每张牌有一个发动概率 $P_i$ 以及伤害 $D_i$，共有$R$回合，每回合会按编号从小到大依次考虑本次游戏中还未发动的卡牌，依次尝试发动，如果发动成功，进入下一回合，求期望伤害之和，共 $T$组数据。
$T\le444,N\le220,R\le132$

思路

$dp_{i,j}$表示前$i$张牌发动了$j$张的概率
求出每张牌发动的概率$sump_i=\sum\limits_{j=0}^rdp_{i-1,j}(1-(1-p_i)^{r-j})$
$dp$可以DP求得
$dp_{i,j}=\sum\limits_{j=0}^r(dp_{i-1,j}(1-p_i)^{r-j}+dp_{i-1,j-1}(1-(1-p_i)^{r-j+1}))$

例题二、Museum

题面见CF113D

思路

解法一、
设$ f_{i, j} $为第一个人在$ i$, 第二个人在$ j$,此时开始,之后在$ t $点相遇的概率.
枚举终点, 做$ n $次高斯消元即可,不过直接这样做是$ O(n^7)$的.注意到每次高斯消元时,$ Ax = B $只有$ B $发生了变化.于是把$ B $改成一个矩阵就可以$ O(n^6)$了.
最后通过$f_{i,j}=\sum\limits_{1\le i\le n}A_if_{i,i}$,令$f_{i,i}=1$就可以求出所有解

解法二、
设$f(i,j)$为第一个人在$i$，第二个人在$j$这种情况的期望出现次数，因为终止状态只会出现0/1，于是期望就是概率了。

三、树形DP

树形DP是指基于树的结构的动态规划，基础的有：

  • 树的直径：DP记录子树内最长路
  • 树的重心：DP记录子树大小
  • 树上最大权独立集：DP记录子树的根是否选择
  • 树形依赖背包：在dfs序上DP(即每次选择是否跳过子树)，或通过父节点的DP值传入孩子DP
  • 虚树：在原树上只保留需要的点与他们的LCA的树称为虚树，建树方法为：将点按dfs序排序，一次将点加入，用一个栈维护树上的已加入的点和他们LCA的右链，每次加入一个点，与栈顶比较，便可以建出虚树
  • …

例题一、大工程

题面见P4103

解答

有着询问的和小于的限制的题是虚树的一个显著的特征。
建出虚树, 然后直接在上面树形DP。设$ f_i $为以$ i $为根的子树内路径的代价和,$ size_i $为$ i $的子树中询问点的个数,$ max_i $为$i$子树内的到$ i $的最长路,$ min_i $为最短路，则：
$f_i=f_{son_i}+size_i\times k-size_{son_i}$
$max_i = \max\left\{max_{son_i} + 1\right\}$
路径和答案是$ f_{root}$, 对于每个点,用它的最大与次大的儿子更新答案.如果他是被询问的点,则还可以用它每个儿子更新答案.

四、状态压缩DP

基于状态压缩的DP是由于状态用单个简单的变量直接存储存在空间的浪费，而采用压缩的状态的动态规划，例如：

  • 插头DP：维护当前已决策和未决策的一条$Z$字形的轮廓线的插头状态，用括号序列配对插头，每次只需分情况讨论即可，但是这类DP的显著特点就是情况繁多，使用时须细心

例题、

给一个$N$个点$M$条边的无向图，每个点有点权$A_i$，保证任意两点之间距离不超过$10$。
现在要你选取一些点，使得每个点要么自己被选，要么相邻的点被选。
一个方案的代价定义为选取的点的点权和，求最小代价。
$N\le20000,M\le25000,0\le A_i\le10000$

解法

考虑如何利用 “距离不超过10” 这个限制.
不妨把生成树搞出来,那么这个树的深度$ \le 10$. 一个很显然的想法是DP时,对每个点设状态$ dp_{u, S}$, 表示以$ u $为根的子树,当$ u $到根这条路径上的点的选取情况是$S $时的最小代价.
由于,一个点可能会对通过非树边覆盖祖先,对于$S$中每个未选取的点,我们可以再记录一下它是否已经被覆盖.对于一个点状态数是$3^{10}$的.
用$3$进制来表示$S$. 规定一下$S$中某一位的值的意义:

  • 0: 这个点被选取了
  • 1: 这个点未被选取, 但已经被覆盖
  • 2: 这个点未被选取, 且仍未被覆盖

在DFS序上做即可.转移并不困难,注意的是当DFS序中前一个点不是当前点的父亲时,要把$dp$值维护一下.
使用滚动数组,空间复杂度$ O(N + M + 3^{10})$,时间复杂度$O(M + 3^{10}N)$.对每个连通块都要做一遍.

例题一、

对于任意一个正整数$N\le10^5$，求出${1,2,…,N}$的满足”若$x$在该子集中，则$2x,3x$不能在该子集”的子集个数。答案对$10^9+1$取模。
$N\le10^5$

思路

将题目转化为“一个网格图，相邻点不能选”的计数问题，枚举左上角就行了。

五、DP套DP

某些DP问题的子判定问题不能简单的解决,而必须用另一个DP解决,此时就只能使用DP套DP的方法,即：外面的DP的状态是存的里层DP各个状态的值,利用里层的状态来判断外层的DP是否合法,类似的问题有LCS为定值的序列的方案数等等。

例题一、

给你一个只由$ACGT$组成的字符串$S$，对于每个$0\le k\le |S|$，问有多少个只由$ACGT$组成的长度为$M$字符串$T$，使得$LCS(S,T)=k$.
$|S|\le15,M\le10^3$

思路

DP套DP，
算LCS的DP为$dp_{i,j}=max(dp_{i-1,j-1}+[T_i=S_i],dp_{i-1,j},dp_{i,j-1})$
这题的$ |S| $很小,不妨对于每个$ i$, 将$ j $不同时的DP值都记录下来,计个数即可.
但是直接记DP值状态数会爆内存,但是注意到相邻的DP值只会差$1$,所以我们可以用$ 2^{|S|} $的状态数将这些值记录下来.

六、DP的形式优化

有时在做一个DP问题时将会遇到时间或者空间复杂度过高的问题,而在DP的形式上优化便是有效的优化技巧, 典型的有预处理, 分阶段DP等:

  • 预处理: 我们可能发现, 在DP的过程中, 出现了重复的运算, 浪费了时间, 所以我们可以通过DP前预处理, 或者DP过程总处理出最值, 而达到为后面的DP提供便捷的功能与作用, 达到优化的目的
  • 分阶段DP: 在某些DP中将DP拆为一个个有特点阶段也许比将整个DP放在一起更加节省时间与空间, 所以对于彼此相对无关的转移, 可以分开考虑

例题一、

给定长度为$N,M$的数组$A,B$，求最长公共上升子序列。
$N,M\le5000$

思路

状态设计：$dp_{i,j}$表示$A$考虑到$i$，$B$考虑到$j$且必须选$j$的长度
当$A_i=B_j$时，有转移
$dp_{i,j}=\max\left\{dp_{i-1,k}|k<j,B_k<B_j\right\}+1$
由于$A_i=B_j$，这个限制事实上就是$B_k<A_i$，对于同一个$i$限制是相同的。
我们可以从小到大枚举$j$，维护$\max\left\{dp_{i-1,k}|k<j,B_k<A_i\right\}$，直接转移即可。

例题二、

现在有$n$个活动，每个活动需要占用$[l_i,r_i)$的时间，现在有两个会场，两个会场不能同时有活动，但是一个会场可以同时举办多个活动。
要求安排每个活动在哪个会场举行，或者不举行，使得举行活动较少的会场举行活动最多。同时，对$i\in[1,n] $求出如果强制活动$i$必须举行，那么所求答案是多少。
$n\le200$

思路

第一问，预处理出$[l,r)$表示$[l,r)$包含多少段区间，设$f_{i,j}$表示考虑了$[0,i)$区间，第一个会场举办$j$个活动的前提下，第二个会场最多举办多少活动。
第二问，处理出DP数组的前后缀，对于每个询问合并答案
令$g_{i,j}$表示考虑了$[i,size)$这个区间时的DP数组，不难想到：处理出$max_{l,r}$表示$[l,r)$区间一定选时的答案，然后合并前后缀。
考虑优化合并过程，我们发现前缀和后缀都具有单调性，双指针即可。
最终复杂度$O(n^3)$

七、决策单调性优化

DP问题的转移往往需要大量的时间, 如果我们能发现一些性质, 找到一些规律来优化 DP 决策转移的过程, 那么在时间上我们便能得到很大的优化, 常见的有四边形不等式优化, 以及一些1D/1D动态规划的优化。

四边形不等式优化

对于形如以下DP:
$f_{i,j}=f_{i,k-1}+f_{k,j}+w_{i,j}$
如果$w$满足四边形不等式：

  • 任意$i\le i’\le j\le j’$，有$w_{i,j}+w_{i’,j’}\le w_{i’,j}+w_{i,j’}$
  • 任意$i’\le i\le j\le j’$，有$w_{i,j}\le w_{i’,j’}$

那么也可证明：$f_{i,j}+f_{i’,j’}\le f_{i’,j}+f_{i,j’}$
而如果得到了这样的式子, 则就可以证明$ f_{i, j} $的决策一定在$f_{i, j − 1} $与$ f_{i − 1, j} $的决策之间:
$s_{i,j-1}\le s_{i,j}\le s_{i-1,j}$
四边形不等式的证明：http://wenku.baidu.com/link?url=344UHCQdTP9z2dFTCCGB3eBYHnlBeF0IAYdFeLmA_p0QU9nGv3L-6AyISk4zUKcTMBDrokvx_i-5BHh7H5ZFfjS3hf2j9jHdPCgUXwQjqS

1D/1D动态规划方程的优化

$f_i=\min\left\{f_j+w_{j,i}|j\le i\right\}$
若$w$满足四边形不等式，则可证明$f_i$的决策也一定单调。

例题一、NOI2009 诗人小G

题面见P1912

思路

首先推出DP方程:$f_i=\min\left\{f_j+|sum_i-sum_j-l|^p\right\}$
令$w_{i,j}=|sum_i-sum_j-l|^p$，可以证明（不会证）$w$满足四边形不等式。
由上述结论，对于任意的$i\le j$，$f_i$的决策一定$\le f_j$的决策，于是我们用一个栈来维护DP的决策。
图解决策过程

八、斜率优化

斜率优化DP是当DP转移式形如
$f_i = \min\left\{f_j + k_ix_j + c_i + b_j\right\}$
将与$ j $无关的常数提出$ \min$，我们就是要求
$\min\left\{k_ix_j + f_j + b_j\right\}$
令$ y_j = f_j + b_j$，每次我们实际上是在所有过 $(x_j , y_j )$ 且斜率为$-k_i $的直线
$y_j =-k_ix_j+B$
中找到一个直线具有最小的$ B$，即纵截距最小。显然最优的$(x_j , y_j ) $一定在凸壳上。于是我们便可以使用维护凸壳来将时间复杂度变得更优。
根据$ x_j $和$ k_i $的单调性，我们可以：

  • $x_j $与$ k_i $同时单调: 单调队列/单调栈 (hdu 3507)
  • $x_j $单调,$ k_i $不单调: 单调队列/单调栈+二分斜率 (bzoj 2726)
  • $x_j $不单调: Splay维护凸壳 (bzoj 1492)

九、凸单调性DP优化

例题一、IOI2016 aliens

题面见uoj240

思路

将主对角线一边的点翻到另一边，去除一些无用点，首先可以推出一个显然的DP方程
$dp_{i,j}=\max\limits_{k<j}\left\{dp_{i-1,k}+(x_j-y_{k+1}+1)^2-\max(0,x_k-y_{k+1}+1)^2\right\} $
其中$dp_{i,j}$表示用$i$个正方形覆盖$j$个点所需要的最小并面积。
这个转移方程可以很容易斜率优化，时间复杂度就变成$O(nk)$
当然这并不能满足题目要求。
如果$dp_{k,n}$是一个关于$k$的凸函数，那么不妨二分$dp_{k-1,n}$和$dp_{k,n}$这两个状态之间的差值（用一个一次函数取切，得一个切点）。
将DP方程改为$dp_i=\max\limits_j<i\left\{dp_j+(x_i-y_{j+1}+1)^2-\max(0,x_j-y_{j+1}+1)^2\right\}+x$
转移一次有$x$的代价，记录一下$dp_n$转移达到最优值所需要的最少转移次数，就可以二分了。

十、容斥DP

例题一、

给定$n$个数$a_1,a_2,…,a_n$，将这些数分成两组，使得两组中的元素$or$和相同，求方案数，答案对1e9+7取模。
$n\le50,0\le a_i\le2^{20}$

解法

按位考虑, 如果所有的数在某一位上都为$ 0$, 显然可以不用考虑.对于其它的位, 如果要满足题目的要求, 则必须满足所有这一位为$ 1$的数不能全部在同一组里. 虽然这个条件不好计数, 但是它的反面是很好计数的!
所以, 枚举至少有哪些二进制位不满足条件, 然后用并查集维护一下就行了.

例题二、

给定一个$N$维超立方体，第$i$个维度的长度为$r_i$，同时给你一个$N$维超平面$x_1+x_2+…+x_n=S$。这个超平面把超立方体切成至多两部分，求圆点所在那一部分的面积。
$N\le500,A_i\le500,S\le10^9$

思路

有点超纲。。。学了微积分再补

例题三、[ZJOI2016]小星星

题面见P3349

思路

首先考虑一个错误的树形DP. 设$ dp_{u, p} $表示考虑了以$ u $为根的这个子树, 并且根映射到原图的$ p $点. 这个显然可以$ O(n^3) $转移, 但是有什么问题呢?
不同的点可能映射到同一个点. 于是考虑容斥.
求出$ dp_S $表示映射的点集至多为$ S $时的答案, 然后就可以$O(2^nn^3) $做了.

容斥何时起作用

  • $=$和$\not=$
  • $\min$和$\max$
  • gcd和lcm
  • “恰好”和”至少”
  • …

容斥的理解

给定一些条件，问全部满足的对象的个数
答案$=$所有对象$-$至少不满足其中一个的$+$至少不满足其中两个的$-$至少不满足其中三个的…
另一种理解：在所有物品中, 问在某个条件$C_0$下所有物品的贡献之和.构造一些相对容易计算贡献的条件$C_1,…,C_n$再对于每个条件构造容斥系数 $f_1,…,f_n$ 满足对于每个物品
$\sum\limits_{i=1}^{n}s_{C_i}f_i=s_{C_0}$
其中$s_{C_i}$表示这个物品在条件$C_i$下所产生的贡献.对于常见的计数问题, 物品的贡献只会是$0/1$, 表示这个物品是否满足此条件.

凑系数

一个经典的错排问题

求长度为$n$的排列$a_1,…,a_n$的个数，满足$a_i\not=i$
错排数：排列的不动点，即$a_i=i$的位置.

例题四、小学奥数（雾）

给定$m$个数$a_1,a_2,…,a_n$，统计$[1,n]$的整数中，满足$a_1,a_2,…,a_n$中有奇数个数整除它的个数。
$n\le10^9,m\le15$

思路

枚举$m$个数的一个子集，算出$lcm$，容斥一下。
对于每个数，如果它被$k$个数整除，则有
$\sum\limits_{i=0}^{k}C^i_kf_i=k\mod 2$
可以求出所有的$f_i$

例题五、异或图

题面见bzoj4671

思路

容斥。首先枚举子集划分，强制连通性“至少”是这个划分，也就是说，不同子集的两个点之间一定没有边，相同子集的两个点则任意.
对于一个有$m$个联通块的图，容斥系数需要满足
$\sum\limits_{i=1}^{m}$

例题六、[NOI2009]管道取珠

题面见P1758

技巧：平方处理

思路

统计平方的和, 转化成统计有序对.
即统计有多少对$(wayA, wayB)$使得$wayA, wayB$均能得到相同的结果.

例题七、

给定$S, T, K,$求每次$+1, −1,$用不超过$K$次操作从$S$变成$T$的方案数.每一时刻都不能为负
$S,T,K\le10^5$

技巧：反射法

在平面直角坐标系中画出图像($x $轴代表时间,$ y $轴代表当前的数值), 发现所有不合法的路径都可以沿$ y = −1 $反射到一条从$(-(S + 2), 0) $到$ (T, 0) $的路径.
直接组合数计算即可. 当然直接减一下转化为不能穿过对角线也是一样的.