动态规划的各种优化 | 清逸

动态规划的各种优化 | 清逸

题意：产品的生产需要$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)$

Read full article from 动态规划的各种优化 | 清逸