题解：P10978 Fence

前置知识：单调队列。

• 如果让第 $i$ 个工人一块木板都不刷，那么 $f_{i,j}=f_{i-1,j}$。
• 如果让第 $j$ 块木板不被刷，那么 $f_{i,j}=f_{i,j-1}$。
• 如果让第 $i$ 个工人刷第 $k+1$ 块到 第 $j$ 块木板，那么 $\begin{aligned}f_{i,j}= \max_{j-l_i \le k \le s_i-1} \{{f_{i-1,k}+p_i \times(j-k)}\}\end{aligned}$。
  其中 $j$ 应满足 $j\ge s_i$。

#include<bits/stdc++.h>
using namespace std;
struct nod
{
	int l,p,s;
}a[16005];
int f[105][16005],q[16005];
int cmp(nod a,nod b)
{
	return a.s<b.s;
}
int work(int u,int v)
{
	return f[u-1][v]-a[u].p*v;
}
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=k;i++)
		cin>>a[i].l>>a[i].p>>a[i].s;
	sort(a+1,a+k+1,cmp);
	for(int i=1;i<=k;i++)
	{
		int h=1,t=0;
		for(int j=max(0,a[i].s-a[i].l);j<=a[i].s-1;j++)
		{
			while(h<=t&&work(i,q[t])<=work(i,j))
				t--;
			q[++t]=j;
		}
		for(int j=1;j<=n;j++)
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			if(j>=a[i].s)
			{
				while(h<=t&&q[h]<j-a[i].l)
					h++;
				if(h<=t)
					f[i][j]=max(f[i][j],work(i,q[h])+a[i].p*j);
			}
		}
	}
	cout<<f[k][n];
	return 0;
 } 

总结(与本题无关)

• 单调队列或单调栈的核心思想：及时排除永远不可能成为最优决策的决策。
• 能使用单调队列优化的 dp 方程的基本结构：
  $\begin{aligned} f_i= \max_{L(i)\le j \le R(i)} \{f_j+val(i,j)\}\end{aligned}$
  上面转移方程中最大值可替换成最小值。
  详细解释一下：$L(i)$ 和 $R(i)$ 是关于变量 $i$ 的一次函数，可以限制 $j$ 的范围并保证上下界变化的单调性。
  $val(i,j)$ 是关于 $i$ 和 $j$ 的多项式函数，且 其中每部分只与一个变量有关，这是能使用单调队列的基本条件，可以简单理解为当一个变量变化时，较优的决策仍会较优，不会产生乱序的现象。
  顺带一提，$val(i,j)$ 的形式往往决定需要用什么样的优化策略。
• 基本步骤：
  1.当范围缩小时，从队首将不符合范围限制的决策出队。
  2.有新决策加入队列时，在队尾检查单调性，将无用决策从队尾出队，最后把新决策入队。
  3.查询最优决策时，队首即为所求。