$f(i,j)$: 安排前 $i$ 个工匠粉刷前 $j$ 块木板(可以有空着不刷的),工匠们能获得的最大报酬;

(1)第 $i$ 个工匠可以什么也不刷,此时：$f(i,j) = f(i-1,j)$;

(2)第 $j$ 块木板可以 空着 不刷,此时：$f(i,j) = f(i,j-1)$;

(3)第 $i$ 个工匠粉刷 $[k+1,j]$ 的木板，总数不超过$L_i$且必须包含$S_i$，

故：$k+1<=S_i<=j  即  k<=S_i-1;  j-k<=L_i  即  k>=j-L_i$

$f(i,j)=max\{ f(i-1,k) + P_i*(j-k) \}  (j-L_i<=k<=S_i-1, j>=S_i)$

优化：（细节请参考《算法竞赛进阶指南》 P315）

考虑内层循环$j$以及决策$k$时,可以把外层$i$看作定值,状态转移方程可改为：

$f(i,j)=P_i*j + max\{ f(i-1,k)-P_i*k \} (j-L_i<=k<=S_i-1, j>=S_i)$

当$j$增大时,决策 $k$ 的取值范围上界$S_i-1$不变，下界$j-L_i$变大，按与“最大子序列和”一题类似的想法，我们比较任意$2$个决策$k_1$和$k_2$，不妨假设$k_1<k_2<=S_i-1$：

因为$k_2>k_1$，随着j增大，$k_1$会比$k_2$更早从范围$[j-L_i,S_i-1]$中被排除，如果还满足:

$f(i-1,k_1)-P_i*k_1<=f(i-1,k_2)-P_i*k_2$,那么就意味着$k_2$比$k_1$更优且存活期更长。

这种情况下,$k_1$就是无用决策，从候选集排除即可。

综上所述，可以维护一个决策点$k$单调递增，数值$f(i-1,k)-P_i*k$单调递减的队列。

只有队列中的决策才有可能在某一时刻成为最优决策。

该单调队列支持如下操作：

1、$j$变大时，检查队头，把小于$j-L_i$的决策出队；

2、需要查询最优决策时，队头即所求；

3、新决策需要加入候选集时，在队尾检查$f(i-1,k)-P_i*k$的单调性，把无用决策出队，最后新决策入队。

具体操作：

内循环开始时($j=S_i$)，建立空队列，把$[max(S_i-L_i,0) , S_i-1]$中的决策加入候选集(操作$3$).对于每个$j=S_i$~$N$,

检查决策合法性(操作$1$),然后取队头为最优决策(操作$2$)进行状态转移。

每个决策最多入队、出队$1$次，故转移时间复杂度均摊$O(1)$,整体时间复杂度$O(NM)$