自动搬运

查看原文

来自洛谷，原作者为

	Eznibuil whk 失败者 | 谁念征人苦，孤军夜夜归 | /article/rrrtvz2o

搬运于2025-08-24 22:47:06，当前版本为作者最后更新于2024-10-29 14:22:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这三种转移实在不是很优雅。给它改一下，把洞也加入状态，改成：

1. 如果 $(i,x)$ 不是洞，$(i,x)\to(i,x+1)$，代价 $0$。
2. 如果 $(i,x)$ 是洞，$(i,x)\to(i+1,x)$，代价 $0$。
3. 如果 $(i,x)$ 是洞，$(i+1,x)\to(i,x)$，代价 $0$。
4. 如果 $(i,x)$ 是洞，$(i,x)\to(i,x+1)$，代价 $1$。

记 $f_{i,x}$ 表示从 $(i,x)$ 出发的答案。如果有一列没有任何洞，那么这一列的 $f$ 值都与下一列相同。于是离散化。

因为一个格子没有洞的话只有一种转移，所以不用动它。最后转移的数量和洞的数量就线性相关了，倒着计算即可。

设洞数量 $K=\sum_ik_i$，时间复杂度 $O(n+z+K\log K)$。

#include<algorithm>
#include<iostream>
int dp[100001];
long long e[2000001];
int main()
{
	std::cin.tie(0)->sync_with_stdio(0);
	int n,x,z,le=0;
	std::cin>>n>>x>>z;
	for(int i=1;i<=n;i++)
	{
		int k;
		std::cin>>k;
		while(k--)
		{
			int j;
			std::cin>>j,e[le++]=(1ll*j)<<18|i;
		}
	}
	std::sort(e,e+le,std::greater<>());
	for(int i=0;i<le;i++)
	{
		const int j=e[i]&(1<<18)-1;
		dp[j]++,j<n?dp[j]=dp[j+1]=std::min(dp[j],dp[j+1]):0;
	}
	while(z--)
	{
		int p;
		std::cin>>p,std::cout<<dp[p]<<'\n';
	}
	return 0;
}

Bonus：该题可以使用 01BFS 做到完全线性。