自动搬运

查看原文

来自洛谷，原作者为

	櫻尘ིོི༹ 政委！好！

搬运于2025-08-24 22:37:40，当前版本为作者最后更新于2022-03-02 23:19:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人题解

Subtask 0

暴力枚举每片叶子用哪个画笔画，画哪些叶子能使美观值最大。

裸搜。

时间复杂度 $O(n^m)$

Subtask 1

考虑 dp 。

将画笔按长度从小到大排序，将叶子按美观程度从小到大排序。

每次选出一片叶子后，看用至少用哪支画笔可以画，则它后面的每一支画笔都可以画。

for(int i=1;i<=m;++i){
	int v,s;
	int p=lower_bound(c,c+n,s)-c;
	for(int j=n;j>=p+1;--j)dp[j]=max(dp[j],dp[j-1]+1);
}

计算美观值最大同理。

for(int i=1;i<=m;++i){
	int v,s;
	int p=lower_bound(c,c+n,s)-c;
	for(int j=n;j>=p+1;--j)dp[j]=max(dp[j],dp[j-1]+v);
}

时间复杂度 $O(nm)$

Subtask 2

正解贪心。

将画笔按长度从大到小排序，将叶子按美观度从小到大排序。

由于与越长的画笔匹配的叶子理应美观度越大，且边长小的叶子也能与长的画笔匹配。所以让长度长的画笔匹配满足条件下最大美观度的叶子一定不亏，反复执行这样不亏的操作，最后得到的即是最优解。

适用于维护最长以及美观度最大，但维护美观度最大需要用优先队列维护。

priority_queue<int> q;
int head=1;
for(int i=1;i<=m;++i){
	for(int j=head;j<=n;++j){
		if(a[j].s>c[i]||blog){
			head=j;
			break;
		}
		q.push(a[j].v);
		if(j==n)blog=true;
	}
	if(!q.empty())sum+=q.top(),q.pop();
}

时间复杂度 $O(n \log n)$