先把工匠按S排序，消除后效性．
f[i][j]表示用前i个工匠粉刷前j块的最大价值(允许有一些地方不被刷)

接下来转移:
有两个转移是显然的:这个工匠不刷:$f[i-1][j]$
这个格子不刷:$f[i][j-1]$

刷的话,我们要再所有可能的起始点里面取最大值.不妨设这一次刷的是$[k+1,j]$
$$\max_{j-l_i\le k<s_i} f[i-1][k]+p_i*(j-k)\ (j\ge s_i)$$

这样子没法优化,把$j$拿出来,让值的部分只与$k$有关.
$$p_i\*j+\max_{j-l_i\le k<s_i} f[i-1][k]-p_i\*k\ (j\ge s_i)$$

接下来是lyd老师的做法
可以发现,当$j$增加,$k$的取值范围上界一定,下界递增.用一个下标位置递增,对应的$f[i-1][k]-p_i\*k$递减的单调队列维护.
如果存在$k1<k2<s_i,f[i-1][k]-p_i\*k1\le f[i-1][k]-p_i\*k2$,那么直接把$k1$从队列中删除,维护单调性.
具体地,先把所有$j-l_i\le k<s_i$的$k$插入到队列中.
然后如果$j\ge s_i$,删除队首直到队首$k$满足$j-l_i\le k<s_i$,此时的$k$就是最优的.

时间复杂度$O(nm)$,可以通过代码

事实上我们可以不用单调队列!
再看一下这个式子$$p_i\*j+\max_{j-l_i\le k<s_i} f[i-1][k]-p_i\*k\ (j\ge s_i)$$
随着$j$增加,$k$的集合单调缩小.但如果我们让$j$减小,$k$的集合就单调增大.
用变量维护法.维护一个变量$maxv$表示当前的最优值.
先倒序循环$j=s_i+l_i-1\rightarrow s_i$,如果$j\ge l_i$,就用$f[i-1][j-l[i]]-p[i]\*(j-l[i])$更新$maxv$.然后用$maxv$更新$f[i][j]$
做完这种转移后,再枚举所有$j$,用前面两种转移去转移.
时间复杂度也是$O(nm)$,但更好写.
代码