自动搬运

查看原文

来自洛谷，原作者为

	Reply_ 我恨快速幂

搬运于2025-08-24 22:11:15，当前版本为作者最后更新于2023-05-24 22:05:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意简述

• 给出旅馆中所有房间的空闲情况，求从第 $s$ 天到第 $t$ 天的住房方案 。

• 要求方案的字典序最小(重要！！！)。

• 若不存在这样的方案，输出一行“Not available”。

题目分析

• 第一眼贪心，打了一个发现出问题，于是开始考虑别的算法(看算法标签)。

• 明显这道题要用 dp ，然后我们会发现正着推它不好推，所以我们考虑倒着推，从 $t-1$ 开始倒着推到 $s$。

• 定义 $f_{i,j}$ ：第 $i$ 天在 $j$ 号房入住时共换了几次房，一开始全赋值为最大值即可。

• 定义 $g_{i,j}$ ：第 $i$ 天在 $j$ 号房号房入住时第 $i+1$ 天能到换房次数最少、字典序最小的房间编号。

• 因为房间变了换房次数就要 +1，所以有如下状态转移方程： $f_{i,j}=\min(f_{i,j},f_{i+1,k}+(j\neq k))$，$g$ 数组在 $f$ 更新时顺便记录即可

转移：

for(int i = t-1;i>=s;i--)
	{
		F(j,1,m)
		{
			F(k,0,m)
			{                          
				if(c[i+1][k]=='X' || c[i][j] =='X') continue;//判断该状态合法以及转移而来的状态合法
				int nw=f[i+1][k]+(j!=k);
				if(f[i][j]>nw&&k!=0)
				{
					g[i][j]=k;//顺带转移了g数组
				}
				f[i][j]=min(f[i][j],f[i+1][k]+(j!=k));
			}
		}	
  

输出

这里也是有点难度(对于我来说)，卡了我有一会儿

for(int i = s;i<=t;i++)
	{
		if(g[i][w]!=w)
		{
			if(w<1 || w>26) return;
			cout << char((w+'A'-1));
			cout << ": "<<nw << "-"<<i+1<<'\n';
			w=g[i][w];
			nw=i+1;
		} 
	}

其他的代码希望读者自行编写

另外，感谢某位不愿透露姓名的同学的帮助给予一些思路