题面

题目描述

　　南非世界杯组委会指定了在此期间可提供的一些旅馆供球迷租赁，名为阿凡达的即是其中一所。因为阿凡达旅馆房子的数目不超过26，所以它们可以用26个大写字母表示。
有一天，刘经理的电话响了，他接到了一个租赁房屋的请求，要求从6月12日晚起租到6月19日中午。于是他察看了预定表，但是并没有发现一间房屋能够直接满足要求。比如房主可能因为一些私人原因需要留在自己的房子中，所以这个游客不得不在其中的一间先住上几天再搬到另一间住上几天。他详细检查了预定表后，对旅客说：“我将你先在B安置3天，再将你安排到F去度过剩余的旅途。”
　　你的目标是使得游客从一间房屋搬到另一间房屋的次数最少。
　　注意在旅馆的计费中，总是将某一天的晚上到第二天的中午视作一天。　　　

输入格式：

　　输入文件包括多组数据。
每组数据输入文件第一行包括两个整数M和N。M表示日程表上的天数，N表示公寓的数目。天数不超过100天，从1开始计数，公寓不超过26个，从A开始计数。
接下来M行，每行包括N个字母，表示从第i天晚到次日中午，该公寓是否已经被出租，X代表被出租，O代表未被出租。
最后一行包括两个整数s,t，代表旅客从第s天晚入住到第(t+1)天中午结束旅行。1<=s M=N=0标志着文件的结束。

输出格式：

　　对于每一组数据，首先打印测试数据的编号，冒号和一个空行。接下来输出换房次数最少的方案，每一行使用如下格式：unit: startdate-enddate 其中unit为房屋编号，startdate和enddate分别为该旅客入住和离开该房屋时间。
注意，如果存在多种方案满足换房次数最少，输出其中字典序最小的方案。
如不存在这样的方案，输出一行”Not available”。
每两组输出之间以一个空行隔开。输出文件的末尾不要加空行。

思路

这种题第一眼：模拟题。确实可以模拟，但是我们发现，模拟的复杂度很高（不过好像也能过），这显然是不允许的，所以考虑优化，发现记忆化效果不错，也就是说，这是一道 DP 题。

我们可以让 $dp[i][j]$ 表示第 $i$ 天至第 $j$ 天中转次数，那就是经典的区间 DP 了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

int n, m;
char a[110][110];
int s, t;

int dp[110][110];
int d[110][110];

void Input() {
    scanf("%d%d", &n, &m);
    if(n == 0 && m == 0) return exit(0);
    for(int i = 1; i <= n; i++) {
        scanf("%s", a[i] + 1);
    }
    scanf("%d%d", &s, &t);
}

void Init() {
    memset(dp, 0x3f, sizeof(dp));
}

void Print(int s, int i, int j) {
    if(i == t) return ;
    if(d[i][j] != j){
        printf("%c: %d-%d\n", 'A' + j - 1, s, i + 1);
        Print(i + 1, i + 1, d[i][j]);
    }
    else Print(s, i + 1, j);
}

void Work() {
    dp[t][0] = 0;
    for(int i = t - 1; i >= s; i--) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == 'O') {
                for(int k = 0; k <= m; k++) {
                    if(dp[i + 1][k] + (j != k) < dp[i][j]) {
                        dp[i][j] = dp[i + 1][k] + (j != k);
                        d[i][j] = k;
                    }
                }
            }
        }
    }
    int ans = 1e9, j;
    for(int i = 1; i <= m; i++) {
        if(dp[s][i] < ans) {
            ans = dp[s][i];
            j = i;
        }
    }
    if(ans == 1e9){
        printf("Not available\n");
        return ;
    }
    Print(s, s, j);
}

int main() {
    int ca = 0;
    while(1) {
        Input();
        printf("Case %d:\n\n", ++ca);
        Init();
        Work();
    }
    return 0;
}