P5486 [JLOI2010]世界杯租房 题解

Reply_ · 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;
        } 
    }

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

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