动态规划的各种优化

Feb 25, 2017 | 算法总结 | 阅读

单调性优化

Vijos 1243 生产产品

题意：产品的生产需要$m(\leq 10^5)$个步骤，每个步骤可以在$n(\leq 5)$个机器中任何一台完成，机器$i$完成第$j$个步骤的时间为$a_{i,j}$。把半成品从一台机器上搬到另一台机器上也需要一定的时间$k$，每台机器最多只能连续完成产品的$l(\leq 5*10^4)$个步骤，问最短需要多长时间。

题解：朴素的动态规划的算法：定义$dp[i][j]$表示前i个步骤，最后一段步骤用第$j$个机器完成，$sum[i][j]$表示前$i$个步骤用第$j$个机器完成的时间。状态转移方程：
$$dp[i][j]=min\left \{ dp[t][p]+(sum[i][j]-sum[t][j])+k \right \},(j\neq p,i-t\leq l)$$
时间复杂度：$O(n^2ml)$。
把方程式变形得：
$$dp[i][j]=min\left \{ dp[t][p]-sum[t][j] \right \}+sum[i][j]+k,(j\neq p,i-t\leq l)$$
发现括号内的式子是根据$t$决定的（枚举$p$和$j$），所以可以用单调队列维护一个单调递增的序列进行优化，时间复杂度：$O(n^2m)$。
code

POJ 3017 Cut the Sequence

题意：给定一个有$n$个非负整数的数列$a(a_i\leq 10^5)$，要求将其划分为若干个部分，使得每部分的和不超过给定的常数$m$，并且所有部分的最大值的和最小。

题解：朴素的动态规划的算法：定义$dp[i]$表示前$i$个数字划分后所有部分最大值的和，$m(l,r)$表示区间$[l,r]$的最大值，$sum(l,r)$表示区间$[l,r]$的和，状态转移方程：
$$dp[i]=min\left \{ dp[t]+m(t+1,i) \right \},sum(t+1,i)\leq m$$
因为是非负整数，dp的值显然是递增的，但是并没有可维护单调的序列，决策点也没有单调性，需要挖掘出单调性，引用kuangbin的做法：

首先假如不考虑m的限制，那么最优决策的$j$点，一定满足$a[j] > max(a[j+1~i])$就是$j$点的值要大于$j+1$到$j$点的值。
很明显的结论，因为假如不成立，那么可以把$j$点也划分到后面去，得到更优的
所以用单调队列维护一个递减数列，这样的话最优决策点只能出现在这些点中。
现在加了$m$的限制，假如上面那个递减数列只有后面一部分是满足$m$限制的。
那么决策点就是上面这些点再加上满足$m$条件的那个边界，所以可以用平衡二叉树维护二叉树里面的值只要随着队列进行维护就好了，可以用multiset实现。

code

斜率优化

BZOJ 1010 玩具装箱toy

题意：$n$个玩具装到若干个容器内，问制作容器费用的最小值。
题解：一份写的不错的题解这里面详细的证明了决策点的单调性，在这前提下利用斜率的单调性，维护单调队列，侧重于“数”。

POJ 1180 Batch Scheduling（批量任务）

题意：有$n(n\leq 10^4)$个任务，要求依次执行，从时刻$0$开始，任务被分批加工。在每批任务开始前，机器需要启动时间$s$。每个任务有相应的执行时间T和影响因素F。一批任务完成时间就是各个任务的完成时间总和，每个任务完成的费用是任务完成时刻*该任务费用系数。确定一个方案使得总费用最小。

题解：这题要倒推，只有后面任务的分配确定后才有意义。
$f(i)$表示完成$i$~$n$任务的最小费用，$T[i,j]$，$F[i,j]$分别表示完成任务$i$~任务$j$所需要的时间和费用。假设新增批次任务$i$~任务$j-1$，那么在$f(j)$的基础上，新增加的完成$i$~$j-1$任务的费用：$(s+T[i,j-1])F[i,j-1]$，延时造成的费用：$(s+T[i,j-1])F[i,j-1]$。所以$f(i)=min(f(j)+(s+T[i,j-1])*F[i,n])$，时间复杂度$O(n^2)$。

利用最优决策点的凸性优化（侧重“形”）：记$x(i)=T[i,n]，y(i)=f(i)，a[i]=s+T[i,n]，b[i]=F[i,n]$。上面的状态转移方程式等价于：$f(i)=min(y(j)+(a[i]-x[j])b[i])$，即$minp=f(i)=-b[i]x(j)+y(j)+a[i]b[i]$，即$y(j)=b[i]x(j)+(p-a[i]*b[i])$。随着$i$递减，$x(i)$递增，斜率$b[i]$递增，所以用单调队列维护一个下凸壳，时间复杂度降为$O(n)$。
code