题解：P10978 Fence

· · 题解

（以下内容受到李煜东《算法竞赛进阶指南》的启发，如有侵权，联系删除。同时鸣谢前辈及更多人做出的贡献。）

前置知识：单调队列。

这道题较为显然的使用 dp。

设 f_{i,j} 表示前 i 个工人刷了前 j 块木板能获得的最大价值，且为了能够转移需要允许前 j 块木板有的不刷。

注意一点，为了保证枚举顺序正确，需先按照 s_i 从小到大排序。

暴力转移是 O(n^2k) 的，这道题重点就在于优化上。

枚举 i 和 j 是必须的，考虑优化掉枚举 k。

先改写一下第三个转移方程，当 i 和 j 固定时，可写为：

\begin{aligned}f_{i,j}= p_i\times j+\max_{j-l_i \le k \le s_i-1} \{f_{i-1,k}+p_i \times k\}\end{aligned}

（为方便表述，将 {f_{i-1,k}+p_i \times k} 设为 g(i,k)）

不难发现，当外层循环 i 不变，内层循环 j 逐渐变大时，k 的范围的下界逐渐增大，上界不变。

似乎是......单调队列？

验证发现，的确满足单调队列的性质，需要维护一个决策点 k 单调递增，g(i,k) 单调递减的队列，只有这个队列中的决策有可能成为某一时刻选择的最优决策。

然后就是经典的单调队列优化 dp。

结合代码食用：

#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;
 }

总结(与本题无关)