[PKU2901]Hotel

很容易想到一个很朴素的状态表示，f[i, j, k, l]表示前i个房间住了j个男的k个女的以及l对夫妇。显然TLE＋MLE！

现在让我们考虑一下这道题的一些有意思的性质。
  • 大部分情况下，把夫妇拆掉会比合起来住更优。考虑一个2人间，如果合起来住，占一间，拆开来和别人住（假设人够多的话），也是占一间；如果是3人间或者更多人一个房间的话，那么合起来住之能够在1间n人间里面住2个人，拆开住却能够在2个n人间里面住2n个人。不管如何，拆开住的房间利用率总是不比合起来住。
  • 但是有一种特殊情况要考虑。比方说恰巧有3対夫妇，有3个2人间，如果按照上面安排的话，就住不下了。但是如果我们让一对夫妇住在一起，那么剩下的人就可以按照上面的做了。这种情况只出现在奇数对夫妇的时候。
根据上述性质，我们可以把l那一维缩减一下，变成0或者1，因为最多安排一对夫妇住在一起。转移方程： 
f[i, j, k, 0] = 
min { f[i-1, j, k, 0],
      price[i] + min{ f[i-1, j-p, k, 0], 
                      f[i-1, j, k-p, 0] } 
}

f[i, j, k, 1] = 
min { f[i-1, j, k, 1],
      price[i] + min{ f[i-1, j-1, k-1, 0],
                      f[i-1, j-p, k, 1],
                      f[i-1, j, k-p, 1] }
}
时间复杂度O(roommalefemale2)，勉强不会超时。但是MLE！解决办法可以：滚动数组，或者跟01背包一样，倒着做，直接覆盖，空间复杂度降到O(malefemale) 
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

#include <cstdio>
#include <cstring>
#include <algorithm>

int TestData, male, female, room, couple, cap[501], price[501], f[501][501][2];
void solve()
{
  scanf("%d%d%d%d", &male, &female, &room, &couple);
  for (int i = 1; i <= room; ++i)
    scanf("%d%d", cap+i, price+i);
  for (int j = 0; j <= male; ++j)
    memset(f[j], 63, sizeof(f[j]));
  f[0][0][0] = 0;
  for (int i = 1; i <= room; ++i)
    for (int j = male; j >= 0; --j)
      for (int k = female; k >= 0; --k)
      {
        int min0 = 0x7FFFFFFF, min1 = 0x7FFFFFFF;
        for (int p = 0; p <= cap[i]; ++p)
        {
#define UP(x, y) if (y < x) x = y;
          if (j-p >= 0)
          {
            UP(min0, f[j-p][k][0]);
            UP(min1, f[j-p][k][1]);
          }
          if (k-p >= 0)
          {
            UP(min0, f[j][k-p][0]);
            UP(min1, f[j][k-p][1]);
          }
        }
        if (j-1 >= 0 && k-1 >= 0 && cap[i] >= 2) UP(min1, f[j-1][k-1][0]);
        UP(f[j][k][1], price[i]+min1);
        UP(f[j][k][0], price[i]+min0);
#undef UP
      }
  int ans = f[male][female][0];
  if (couple) ans = std::min(ans, f[male][female][1]);
  if (ans >= 0x3F3F3F3F)
    printf("Impossiblen");
  else
    printf("%dn", ans);
}
int main()
{
  for (scanf("%d", &TestData); TestData--; ) solve();
}

Comments