动态规划杂题

[更新中]动态规划杂题。

51Nod 1052, HDU 1024 – 最大M子段和

题目链接:51 Nod 1052HDU 1024

思路:$f(i,j)$表示前$i$个必选$i$,分成$j$段的最大和。易推得

$$f(i,j) = \max \{ f(i – 1, j), \max_{j \leq k \leq i – 1} f(k, j – 1) \} + a_i $$

最朴素的做法空间复杂度是$O(nm)$,时间复杂度是$O(n^2m)$,显然不管是$n \leq 5000$(51Nod),还是$n \leq 10^6$(HDU),都是过不了的。

考虑$f(i,j)$的第$j$个状态只和$j – 1$相关,那么这一维度可以使用滚动数组优化。而$\max_{j \leq k \leq i – 1} f(k, j – 1)$也可对$j – 1$的状态维护前缀最大值,这样空间复杂度优化为$O(n)$,时间复杂度优化为$O(nm)$。

HDU 1029 – Ignatius and the Princess IV

题目链接:HDU – 1029

思路:这题有$O(n)$的做法,原型题在《编程之美》中,2.3节《寻找发帖“水王”》。

参考《编程之美》:考虑每次删除两个不同的数字,在剩下的数字中,答案出现的次数仍然超过总数的一半,那么我们可以不断重复这个过程,$O(n)$解决问题。在这个题目中,又一个计算机科学中的普遍思想,就是如何把一个问题转化为规模较小的若干个问题,在转化过程中,小的问题与原问题本质相同。

HDU 1069 – Monkey and Banana

题目链接:HDU – 1069

一个盒子的三边为$(a,b,h)$那么就有$3!=6$种状态。题目提供了几个比较关键的信息,首先是每种类型的砖块都有无限个,也就是我们取了一个盒子的一种状态之后还可以取它的另一种状态,例如$(2,3,4)$可以摆在$(3,4,2)$的上方;而只有满足长和宽都比上一个小的时候才能向上叠加,这又限制了每个盒子的每种状态至多只能取一次(因为不能相等),接着就可以利用类似LIS的思路$O(s^2)$解决了,$s$为状态数,这里可以看作$s = 6 \times n$,而实际上$s \leq 6 \times n$,因为有边相等的情况。

HDU 1074 – Doing Homework

题目链接:HDU – 1074

状态压缩DP。考虑用n个二进制位,第$i$位表示第$i$个作业是否已经完成,维护四个量:从哪一个状态转移过来的,最小花费是多少,已经使用了多少时间以及本次选择的课程是什么。假设状态$j$可以推到$i$,则可以得到状态转移L:

$$ f(i) = \min \{ f(i), f(j) + [t(j) + c_s –  d_s > 0] \cdot [t(j) + c_s –  d_s]  \} $$

其中$t(j)$为到$j$状态为止所花费的时间,$d_s$是当前被选择的课程的DDL,$c_s$为当前被选择课程的消耗时间,那么$[t(j) + c_s –  d_s > 0] \cdot [t(j) + c_s –  d_s]$则为花费。注意完成时间小于DDL的时候是不计算花费的。当$f(i)$每次被更新的时候,更新$t(i) = t(j) + c_s$。

HDU 1087 – Super Jumping! Jumping! Jumping!

题目链接:HDU – 1087

思路:$f(i)$表示以$i$结尾的上升子序列的最大和,注意这里不是LIS的和或者LIS的最大和。不过类似LIS的思路可以推得转移方程:

$$ f(i) = \max_{1 \leq j \leq i – 1} \{ f(j) \} + a_i $$

可以$O(n^2)$解决。有$O(n \log n)$的做法,待补充。

51Nod 1006 – 最长公共子序列LCS

题目链接:51Nod 1006

LCS是经典的动态规划问题,这里记录记录LCS的方法。从后往前遍历$a$和$b$,如果$a_i = b_j$,说明$i$和$j$包含在LCS当中。否则,若$f(i – 1,j) \leq f(i, j – 1)$,说明$j$一定在,若$f(i – 1,j) > f(i, j – 1) $,说明$i$一定在。

51Nod 1134 – 最长递增子序列

题目链接:51Nod 1134

二分栈优化LIS。$b_k$表示LIS长度为$k$的最小$a_i$。

51Nod 1183 – 编辑距离

题目链接:51Nod 1183

思路:$f(i,j)$表示$a[1\cdots i]$和$b[1 \cdots j]$的最小编辑距离。我们可以得到:

$$ f(i,j) = \left \{ \begin{aligned} & \min \{ f(i – 1, j – 1), f(i – 1,j) + 1, f(i, j – 1) + 1 \} & , a_i = b_j \\ & \min \{ f(i – 1, j – 1) + 1, f(i – 1,j) + 1, f(i, j – 1) + 1 \} & , a_i \neq b_j \end{aligned} \right . $$

边界条件$f(i,0) = f(0, i) = i$。

HDU 1257 – 最少拦截系统

题目链接:HDU – 1257

思路:覆盖集中不上升序列的个数等于最长上升序列的长度。

HDU 1160 – FatMouse’s Speed

题目链接:HDU – 1160

思路:对一个维度排序另一个维度求LIS。

51Nod 1007 – 正整数分组

题目链接:51Nod 1007

思路:每个数只有两种状态——在集合A中或者在集合B中。我们可以用$f(i,j)$表示前$i$个物品总和最大为$j$的情况下,总和的最大值。与01背包类似地,可推出转移方程

$$ f(i,j) = \max \{ f(i – 1, j), f(i – 1, j – a_i) + a_i \} $$

限制最大容量为所有数总和的一半,这个时候得到的最大值就是在AB差最小情况下,元素比较少的哪一个集合。已知总和和一个集合中元素的数量,可以求出另一个集合,两集合元素个数作差即为答案。

51Nod 1021 – 石子归并

题目链接:51Nod 1021

思路:区间DP,$f(l,r)$表示$[l,r]$区间归并的最小代价,那么

$$f(l,r) = \min \{ f(l, i)+f(i+1,r) + \sum_{i = l}^{r} a_i \}$$

 

 

 

说点什么

avatar
50
  Subscribe  
提醒