自动搬运

查看原文

来自洛谷，原作者为

	世末OIer **

搬运于2025-08-24 22:27:58，当前版本为作者最后更新于2021-01-09 22:36:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是出题人的小号，拉出来溜溜

首先是20pts的部分分。由于数据开放下载，所以手玩即可。

接下来是正解。

看到格子数很小，所以我们就可以枚举哪一些必须不能被削平（即为峰）。这一步可以用dfs解决。

然后进行dp。（类似于floyd）

	for(int k=1;k<=n*m;++k) for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){  //由于一个格子带来的收益可能会改变整个棋盘，所以需要跑n*m次 
		if(cnnt[i][j]) continue;
		else if(c[i][j]) c[i][j]=max(1,min(c[i][j],min(min(c[i-1][j],c[i][j-1]),min(c[i+1][j],c[i][j+1]))));//取min是为了最小和保证不出现额外的峰，与1取max是为了保证有 
		else c[i][j]=0;
	}

最后判断是不是满足条件即可。

details:

1.你需要满足正视图和左视图。每行每列至少有一个点不能被削掉。贪心的想每行每列只有一个点。

2.判断是否满足有点复杂难写。

总结：

最难想的是这个dp。想到了，你还得需要码力。

Code