题解：P10978 Fence

HZEason_Ai · 2025-04-07 10:07:18 · 题解

题目传送门

说明

本题解默认读者掌握单调队列用法，如若不然，请转向 P2032 扫描。

Solution

先将所有工匠按 s_i 从小到大排序，则问题被转化为线性 DP。

设 f[i][j] 表示前 i 个工匠粉刷到了第 j 个木板所获得的最大报酬，则共有三种转移：

1.第 i 个工匠不参与粉刷，则转移为：

2.第 j 个木板空着不刷，则转移为:

3.设 k 为第 i-1 个工匠粉刷到的右边界，则第 i 个工匠需要粉刷第 k+1 到第 j 个木板，则有转移：

对于第三个转移展开后发现与 k 呈正相关，考虑维护一个单调队列使 f[i-1][k] - p_i \times k 单调递减，每次检查队首的合法性，合法则队首最优，否则出队，与此同时插入新决策并保证队列的单调性，代码如下：

for(int i=1;i<=m;i++)
    {
        int h=0,t=0;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i][j-1],f[i-1][j]);//前两种转移
            if(j>=a[i].s+a[i].l) continue;//不可到达
            while(h<=t&&q[h]+a[i].l<j) h++;//队首元素不合法
            if(j<a[i].s)
            {
                while(h<=t&&f[i-1][q[t]]-q[t]*a[i].p<f[i-1][j]-j*a[i].p) t--;
                q[++t]=j;
            }
            else f[i][j]=max(f[i][j],f[i-1][q[h]]+a[i].p*(j-q[h]));
                //转移时，应满足j+a[i].s
        }
    }

因为每次决策时至多入队或出队一次，故转移复杂度为 O(1)，所以整个程序复杂度为 O(mn)，可以通过此题。

AC代码

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define er puts("")
#define sc putchar(' ')
using namespace std;
const int N=1.6e4+5,M=1e2+5;
int q[N],f[M][N];
struct node{
    int l,p,s;
}a[N];
bool cmp(node x,node y){return x.s<y.s;}
int read()
{
    int x=0,a=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') a=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
    return x*a;
}
void write(int x)
{
    if(x<0) x*=-1,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
signed main()
{
    int n=read(),m=read();
    for(int i=1;i<=m;i++) 
        a[i].l=read(),a[i].p=read(),a[i].s=read();
    sort(a+1,a+1+m,cmp);//转化为线性DP
    for(int i=1;i<=m;i++)
    {
        int h=0,t=0;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i][j-1],f[i-1][j]);//前两种转移
            if(j>=a[i].s+a[i].l) continue;//不可到达
            while(h<=t&&q[h]+a[i].l<j) h++;//队首元素不合法
            if(j<a[i].s)
            {
                while(h<=t&&f[i-1][q[t]]-q[t]*a[i].p<f[i-1][j]-j*a[i].p) t--;//保证单调
                q[++t]=j;//入队
            }
            else f[i][j]=max(f[i][j],f[i-1][q[h]]+a[i].p*(j-q[h]));
                //转移时，应满足j+a[i].s
        }
    }
    write(f[m][n]);
    return 0;
}