专栏文章

题解：P10978 Fence

HHZEason_Ai
P10978题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipoxx5f
此快照首次捕获于
2025/12/03 15:33
3 个月前
此快照最后确认于
2025/12/03 15:33
3 个月前
查看原文
题目传送门

说明

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

Solution

先将所有工匠按 sis_i 从小到大排序，则问题被转化为线性 DP。
设 f[i][j]f[i][j] 表示前 ii 个工匠粉刷到了第 jj 个木板所获得的最大报酬，则共有三种转移：
1.第 ii 个工匠不参与粉刷，则转移为：
f[i][j]=f[i−1][j]f[i][j]=f[i-1][j]
2.第 jj 个木板空着不刷，则转移为:
f[i][j]=f[i][j−1]f[i][j]=f[i][j-1]
3.设 kk 为第 i−1i-1 个工匠粉刷到的右边界，则第 ii 个工匠需要粉刷第 k+1k+1 到第 jj 个木板，则有转移：
f[i][j]=max⁡j−li≤k≤si−1{f[i−1][k]+pi×(j−k)},且满足j≥sif[i][j]=\max_{j-l_i\le k \le s_i-1} \{f[i-1][k]+p_i \times (j-k) \}\text{,且满足}j \ge s_i
对于第三个转移展开后发现与 kk 呈正相关，考虑维护一个单调队列使 f[i−1][k]−pi×kf[i-1][k] - p_i \times k 单调递减，每次检查队首的合法性，合法则队首最优，否则出队，与此同时插入新决策并保证队列的单调性，代码如下：
CPP
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(1)，所以整个程序复杂度为 O(mn)O(mn)，可以通过此题。

AC代码

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...