11.2 DP专题——和DP打成一片题解

T1 求三角形的最大面积

题目大意:给你一个由多个三角形组成的大三角形,其中有些三角形缺失了,求出剩下部分最大的三角形。

毒瘤题,dp很好想,被特殊情况坑了。
首先上三角和下三角都要算一遍(其实就是反过来再找一遍)
就拿上三角来说,我们很容易就知道它的高度就是min(左,右)+1,但是实际上还要考虑一些特殊情况

比如下面这种情况:

输入的时候是这样的

所以在更新f[i][j]的时候要注意判断j的奇偶性就行了


T2 下楼问题

题目大意:有一个n层楼的建筑,现在有一只猫在楼顶,每层楼有三个门,现给出距离,求猫到1楼的最长距离(不能上楼也不走回头路)

由于每层楼之间是独立的,而且下了楼就不能往上,所以每层楼的状态具有无后效性,即我们不必关心当前状态是怎么来的。
我们考虑如何更新当前状态

假设我们要更新4这个点,我们发现其余5个点都有到它的合法路径,如果我们用5更新4的话,会发现5状态也会需要4来更新,我更新我自己是不可以的。
于是我们可以只考虑上一层的来更新下一层的

先解释下变量吧,我觉得还是比较形象的

变量名 变量含义
_path[i] 第i层楼左边的路径长度
path_[i] 第i层楼右边的路径长度
down[i] 第i层楼中间门往下的路径长度
down_[i] 第i层楼左边门往右下的路径长度
_down[i] 第i层楼右边门往左下的路径长度
f[i][j] 走到第i层楼第j扇门的最长路

于是状态可以这样更新:
\(f[i][2]=max(f[i+1][2]+down[i+1],max(f[i+1][1]+down\_[i+1]+path\_[i],f[i+1][3]+\_down[i+1]+\_path[i]))\)
\(f[i][1]=max(f[i+1][3]+\_down[i+1],max(f[i+1][1]+down\_[i+1]+\_path[i]+path\_[i],f[i+1][2]+down[i+1]+\_path[i]))\)
\(f[i][3]=max(f[i+1][1]+down\_[i+1],max(f[i+1][3]+\_down[i+1]+\_path[i]+path\_[i],f[i+1][2]+down[i+1]+path\_[i]))\)


T3 瞬移

题目大意:有两个人在一个0-1矩阵上进行移动,其中是不可走的位置。他们每次只能从当前行移动到下一行,而且两个人的位置x,y必须满足限制:\(x+m_i\le y\le x+m_a\) . 一个人移动到下一行的代价为其横坐标变化值的绝对值。问两个人都到达底端需要的最小消耗.

做惯了大数据的题目,做一些比较小的数据的题目都不敢大胆去想了,这题目n只有1000而m只有10,对于师傅和徒弟两个人,我们可以五重循环分别枚举层数 当前徒弟位置 当前师傅位置 上一层徒弟位置 上一层师傅位置 这样的时间复杂度达到了惊人的\(O(NM^4)\)然而由于数据范围较小,所以并不会超时.

我们可以用f[dep][i][j]表示dep层师傅在i徒弟在j时所需要耗费的最小值,枚举上一层的状态即可更新.


T4 数字游戏

题目大意:给你n个数,每个数有一个衰减值,m个回合,每个回合你可以选一个数(选完消失并计入答案),选完后剩余的数衰减。求能选到的最大的总和是多少。

可以比较容易地发现一个结论:如果n=m,就是所有数都会被选到的话,要根据bi的大小来选,先去掉那些每回合损耗多的,再去掉损耗少的,这样显然就是最优的。
但如果m<n呢?设想:假如己经选定了m个数,只去掉这m个数,那么与m=n的情况一样,我们一定是按照bi的大小来去掉的。因为显然对于选定的个数,这样做最优。
到这里,我们就会想到采用动态规划的方法。把n个数按照bi从大到小排序,然后问题就转化为对于一个n个数的序列,从中选择m个数,第i个选择的数权值为A-B*i,(A,B分别为此数在原来a,b数组里对应的值),使得所有权值的和最大。
不难写出下面的动态规划状态转移方程:

$$f(i,j)=max(f(k,j-1)+a_i-b_i \times(j-1)$$
$$f(0,0)=0$$

其中,$$1\le i\le n ,1\le j\le m,0\le k<j$$,ai,bi为排序后第i个数相应的值。这样的复杂度是$$O(n^3)$$

再进一步分析,很容易地把上述动态規划方程改变为下面的形式:
令F(i,j)前i个数当中取了j个数的最优解,则

$$F(i,j)=max(F(i-1,j),F(i-1,j-1)+a_i-b_i\times(j-1)$$
$$F(0,0)=0$$

这样,时间复杂度就降到了$$O(n^2)$$


点赞
  1. Naoh说道:
    Google Chrome Windows 7

    写得好写得好

  2. Nietsne说道:
    Google Chrome Windows 10

    留坑不填,禁赛一年。

发表评论

电子邮件地址不会被公开。必填项已用 * 标注