动态规划

矩阵优化DP

bzoj 4417

按照其给定的棋盘走法,每次走奇数步。那么有\(f_{i,j}=f_{i-1,j\pm 1}+f_{i-3,j\pm 1}+f_{i-5,j\pm 1}…\),
即\(f_{i,j}=f_{i-1,j\pm 1}+f_{i-2,j}\)。

定义矩阵列:\(j \in [0,n-1]\)列表示\(f_{i-1,j}\),\(j \in [n,2n-1]\)列表示\(f_{i-2,j}\)。
\(j \in [0,n-1]\)行表示\(f_{i,j}\),\(j \in [n,2n-1]\)行表示\(f_{i-1,j}\)。
从\(f_{i-2} \rightarrow f_{i}\)转移斜对角线为1。从\(f_{i-1} \rightarrow f_{i-1}\)斜对角线为1。
从\(f_{i-1} \rightarrow f_{i}\)有\(base[i][i-1~i+1]\)为1。
那么矩阵就可以实现转移了。

bzoj 4870
题意:求\(\sum \textrm{C}_{nk}^{ik+r}\)。
设矩阵表示模k余r的和。\(f[i][j]=f[i-1][j]+f[i-1][(j-1+k)\% k]\)。
改改矩阵乘法就好了。

矩阵优化

51nod 1033
因为行数比较少,\(n\leq 5\)。我们用二进制表示当前状态,比如说\(10101\)表示第1,3,5行放了,第2,4没放。用数组\(a[i][j]\)表示状态\(i\)到状态\(j\)的方案数。最终求的是第\(0\)层\(0\)到第\(m\)层\(\underset{m}{1111…1}\)状态的方案数,相当于矩阵\(a^{n+1}\)。

树形DP

前言:

通常的动态规划都是在有向无环图上进行的,无论是线性的还是树形细想:假如有环的话必定没有一个特定的递推顺序,背包问题一般都是线性上的动态规划,我们这里开始了解简单的树形dp。

树形动态规划就是在“树”这种特殊的数据结构上进行的动态规划 ,树形dp通常有两种方向 一种是自顶向下 一种是自底向上

(1)叶—-> 根 :在回溯的时候从叶子结点往上更新信息(没有上司的舞会)
(2)根—-> 叶 :往往是在从叶往根dfs一遍之后,相当于预处理,再重新往下获取最后的答案
树形dp往往都是要利用递归的写法来实现的 dfs
而视题目建立有向图还是无向图 可以减少代码量
没有上司的舞会

题目大意:每个结点给定一个价值,子节点和父亲结点不能同时选取,求能够选取的最大价值

转移方程:
f[u][0]:表示不选择u结点后u子树能够得到的最大值
f[u][1]:表示选择u结点后u子树的能够得到的最大值

$$
f[u][0]=\sum max\{f[u][0],f[u][1]\}
f[u][1]=a[u]+\sum f[u][0]
$$.

 
华丽的吊灯
again:
$$
f[i][j]=max\{ f[i][j-k-w[son] ] + f[son][k] + l[son] \}
$$.

 
拓扑序计数
$$
f[i]=\frac{(size(i)-1)!}{\prod (s[j]!)(j\epsilon son[i])}*\prod f[j],j\epsilon son[i]
$$.
相当于从(size[i]-1)个中取s[j]个的排列组合。
注意有模P以及涉及除法,先处理出逆元。

状态压缩DP

写dp的时候方程中最重要的就是表示状态了。比如说做01背包时,\(dp[i][j]\)表示放第\(i\)个物品的时候容量为\(j\)时的最大价值。这里\(i\)、\(j\)就是状态。
但是有的时候,所需要表示的状态太多,很容易会使空间复杂度爆炸,这时候就需要适当的压缩状态的表示。

tyvj 1059 过河
首先这题很容易想到\(dp[i]=min(dp[i-j])\)的dp。
然而1e9的n,无论是空间还是时间都是爆炸。
其实细想一下,因为石头的个数有限,所以\(dp[i]\)会出现大量的相同状态,这些状态有的对转移根本没有作用。事实上,可以将这些成段的给省略掉。

压缩的根据如下,因为S到T之间都能取,当S=s*(s+1),取特解x=x’+(S+1)*t, y=y’-S*t
会发现x和y总有非负整数解,每次Q加1就相当于少取一个S多取一个(S+1),遇到Q的整数倍表现出周期性。观察到在这种情况下S不大于9,T不大于10。
这样,对于某块石头,如果它后面紧跟着那块石头与它相距超过90,我们可以将从后一块石头开始的所有石头往前移动直到最近的那块与它的距离是90而不改变规划结果。

如果不了解这个压缩方法,其实可以通过预处理与石子有关的格子,然后仅仅对这些格子进行dp就行了。

Continue reading

图上动规

51nod 1274 最长递增数据
因为路径的要求是严格递增的,所以一条边不会经过多次。
考虑\(dp[i]\)表示顶点\(i\)的最长边数。如果考虑从小到大枚举边数,在加入当前边之前的边肯定都比它小,且假设加入的顺序递增。那么加入这条边时,有\(dp[e[i].x] = max(dp[e[i].x],dp[e[i].y]+1)\),反过来还要更新一下边的另一个点\(y\)。这样是完成了一次的更新。另外考虑有很多边一样的情况,此时这些边不满足递增,需要一起操作,由于\(dp\)可能反复更新,需要加个\(tmp\)防止此种情况发生。

数位DP

bzoj 1026 windy数
求\([A,B]\)有多少windy数字.
设\(f[i][j]\)表示最高位为第\(i\)位,且第\(i\)位为\(j\)的windy数的个数。
那么有\(f[i][j]=\sum f[i-1][k]|abs(j-k) \geq 2\)
计算答案的时候,\(count\)记录\(1-(n-1)\)的windy数。
先将最高位为\(1,2,…,base[len]-1\)的统计好,再把最高位、次高位…为\(0\)的统计好,最后统计最高位为\(base[len]\)次高位小于\(base[len-1]\),然后次高位为\(base[len-1]\),次次高位为\(base[len-2]\)的情况,如果出现两位相差低于2的则已经不符合要求了。

bzoj 1833 [ZJOI2010]count 数字计数
求\([l,r]\)中\(k\)出现了几次。
设\(f[i][j][k]\)为\(i\)位,最高位为\(j\),出现\(k\)多少次。

线性模型

线性DP顾名思义就是在一条线上做DP,而且DP一般都是顺序的。当前状态的最优解一定是从前面状态中更新来的。

最长上升子序列

给定一个序列,求最长上升子序列。
可以设\(dp[i]\)表示从1-i,并且以i为最终节点的最长长度,那么有
$$
dp[i]=min(1,dp[j]+1)|a[i]>a[j]
$$
code:

codevs 1576 最长严格上升子序列
codevs 1044 拦截导弹
本质没有区别,事实上是一个最长下降序列。最后需要的导弹数事实上是最长上升序列。

Coprime Sequence
题意:删去一个数,是的所有数的共同gcd最大。
\(f[i][0..1][0..1]\)表示第i个,0删去/1保留,已经删去0..1次。
只需要理清楚这个数删去的gcd是什么 不删的gcd是什么就行了。

区间模型

顾名思义就是在区间上做动规。
一般设\(dp[l][r]\)表示\(l\)到\(r\)上的最优解。
一般的可以从\([l,r]\)推到\([l,r+1]\)或者\([l-1,r]\),也就是说,可以有小区间推到大区间的状态。
所以一般的,区间模型的dp大都是从小区间推到大区间,故外循环一般是区间长度。逐步扩大区间,最终求得\(dp[1][len]\)

最小代价子母树

石子归并
有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。
设\(dp[l][r]\)表示从\(l\)合并到\(r\)的最小代价。
那么很容易有,\(dp[l][r] = min(dp[l,k]+dp[k+1][r]+Sum(l,r)),k=l,l+1,…,r\)
首先外循环是区间长度\(l\),第二层循环循环的是左端点\(i\),那么此时右端点\(j=i+l-1\),第三重循环循环中间断开点\(k\)。

类似题目:
能量项链
几乎一样。
Brackets
考虑\(dp[l][r]\)表示\([l,r]\)的最大匹配数,那么可以有
$$\left\{\begin{matrix}
dp[i][i]=0\\
dp[l][r]=dp[l+1][r-1]+2|s[l] \ matches \ s[r]\\
dp[l][r] = max(dp[l][k]+dp[k+1][r])
\end{matrix}\right.
$$
bzoj 1260
可以用\(f[i][j]\)表示\([i,j]\)最少涂色次数。
$$\left\{\begin{matrix}
f[i][i]=1\\
f[i][j]=min(f[i+1][j],f[i][j-1],f[i+1][j-1]+1)|s[i]=s[j]\\
f[i][j]=min(f[i][k]+f[k+1][j])|i \leq k < j \end{matrix}\right. $$ code:

回文串问题

给定一个回文串,判断\([l,r]\)是否是回文串。
设DP方程\(dp[l][r]\)表示\([l,r]\)是否是回文串。很容易得到这样的关系\(dp[l-1][r+1]=dp[l][r] \ if \ s[l-1]=s[r+1]\)

$$\left\{\begin{matrix}
{dp[l][r]=true,l=r}\\
{dp[l][r]=true,l+1=r,s[l]=s[r]}\\
{dp[l][r]=dp[l+1][r-1],l < r-1,s[l]=s[r]} \end{matrix}\right. $$ codeforces 835d
题意:给一个字符串,求k阶回文串分别有多少,k=1,2,…,n,k阶回文串由两个k-1阶回文串组成。
首先考虑用以上的\(dp\)处理出\([l,r]\)是否是回文串,\(O(n^2)\)
然后,考虑\(f[l][r]\)表示\(l,r\)最多为几阶段回文串,那么有\(f[l][r]=1|dp[l][r]=true\),
如果\([l,mid],[mid+1,r]\)都是k阶回文串,那么\(f[l][r]=f[l][mid]+1\)。做f的过程和做dp的过程差不多,需要考虑的是mid的值要分奇偶讨论。

背包模型

01背包
\(dp[v] = min(dp[v],dp[v-cost[i]]+value[i])|v \ from \ maxv \ downto \ cost[i]\)
code:

hdu 2602

hdu 2546
首先拿出5元买最贵的菜,那么接下来的背包容量为m-5,物品数量n-1,进行01背包就是了。

完全背包
\(dp[v] = min(dp[v],dp[v-cost[i]]+value[i])|v \ from \ cost[i] \ to \ maxv\)
code:

多重背包
给定每个物品的重量、价值和个数,做背包。
可以对个数进行二进制拆分,拆分成\(1,2,4,8,…,num-2^k\),这样可以构成,\(1-num\)的任意数字,做一遍01背包就行了。
复杂度:\(O(v\sum_{i=1}^{n}log_2^{num_i})\)
code:

多重背包优化版

混合背包
综合01、完全、多重三种背包,按每个物品的类型分别做背包。
hdu 5410
可以以这样的方式选取\(A_i*x + B_i\)x为非负整数。
可以先做一次01再做一次完全背包。

二维费用的背包问题
对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为w[i]。
hdu 3496
在N张CD中选M张出来,且选中CD播放时间总和不超过L。使价值总和最大。
这题”二维费用”的条件是以这样一种隐含的方式给出的:最多只能取M件物品。这事实上相当于每件物品多了一种”件数”的费用,每个物品的件数费用均为1,可以付出的最大件数费用为M。
则状态转移方程:\(dp[j][k]=max(dp[j][k],dp[j-1][k-time_i]+value_i)\)。

分组的背包问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
\(f[k][v]\)表示前k组花费v所能取得的最大值。
\(f[k][v]=max(f[k-1][v],f[k-1][v-c[i]]+w[i]|i\in k)\)
hdu 1712
给一个n*m的矩阵,有n种作业,每种作业花费的时间不同获得的价值不同,a[i][j]表示第i种作业花费j天的话收获的价值为a[i][j]。问m天内收获的最大价值。
n种作业相当于n组物品,每组物品又分了若干种,在这里分了m种,已知每种物品的花费和价格,而且同一组的物品时互斥的,即最多选一件。在这里相当于第i种作业要么不做,要么只花费一定天数做一次。
01背包优化掉一维。

有依赖的背包问题
一般有主件和附件之分,附件依赖主件。
可以先对所有的主件做DP处理,再对整体做DP。
hdu 3449
有N个箱子,每个箱子需要花费Ai的代价。箱子里面有K个物品,K个物品你可以选择买任意个,但每个物品只能买一个,每个物品有相应的花费和价值。
你有M的钱,求最多能得到的价值。
先对每个箱子做dp,再对整体dp。

泛化物品
物品并没有固定的费用和价值,而是它的价值随着你分配给它的费用而变化,具有一些函数关系。

拓展
1.输出方案
可以递归求出:

2.输出字典序最小的最优方案
可以用一个栈记录:
hdu 6083

3.求方案总数
\(f[i][v]=sum(f[i-1][v],f[i][v-c[i]])\)
4.最优方案的总数
同3,开个G[i][v]表示最优解个数,记录更新当前状态的pre状态值就行了。

5.求次优解、第K优解
做DP时维护一个序列,表示当前状态的最优解、次优解……