【CF983C】elevator——记忆化搜索

╰半橙微兮° 2021-11-05 05:36 245阅读 0赞

（题面来自luogu）

## 题意翻译 ##

## 题意 ##

一个9层的楼有一个可以容纳4个人的电梯，你要管理这个电梯。

现在各层楼上有一些在排队的人，你知道他们在哪层要到哪层去。你也知道到电梯门口的顺序。根据公司的规定，如果一个人比其他人早到。他也必须先进电梯（无论楼层，只凭时间）。注意人们可以随时离开电梯。

电梯有两个命令：

*  上楼或者下楼， 代价为1
 *  打开当前楼层的门，所有到目的地的人会从电梯里出来，当前楼层排队的人会在**不违反规定的情况下**一个一个进（在电梯还有空间的情况下）（这不是天朝的电梯，不能超员）每个人用1s时间来出入电梯。

最初电梯是空的，在1楼。你需要求出最少用多长时间来吧所有人送回到目的地。最后电梯可以停在任意位置

## 输入输出格式： ##

### 输入格式 ###

*  第一行一个整数n ： 人的数量
 *  下面n行给出每个人的起点、终点。
    
    ### 输出格式 ###
 *  一个整数表示以秒为单位的最小时间

**数据范围**：人数小于等于2000。

\----------------------------------------------------------------------------------

不知道从哪里搞来的这么偏门的考试题……一道很恶心的状压DP，需要压缩的状态是当前电梯内四个人要去的楼层。在设计状态时，要尽可能简化题目中的信息，只抽出那些真正可能影响答案的本质。

由于人是按次序上电梯的，我们只能按编号逐个处理，这一维的转移结构也就确定了。紧接着设计了当前电梯的运行状态这一信息：假设处理时电梯从底下上行而来，回到电梯来的楼层显然会重复状态，是不会更优的。第三维记录电梯所在楼层，第四维则是当前电梯内几个人要去的楼层，0表示空位。这个状态用map压起来，用康托展开也是可以的。

那么每次对于每个状态，如果电梯有人可以下或者下一个要处理的人刚好在这一层，我们就让电梯停下来，贪心地把这些事处理完，再来考虑运行。现在如果电梯停着，我们就让它上下动动；如果正在运行，我们就让它继续沿着当前方向运行，保证不会重复。

代码：

1.  \#include <cstdio>  
2.  \#include <iostream>  
3.  \#include <cstring>  
4.  \#include <algorithm>  
5.  \#include <map>  
6.  \#include <vector>  
7.  \#define mp make\_pair  
8.  \#define st first  
9.  \#define dst second  
10. using namespace std;  
11. void open\_file(string s) \{  
12.     string In = s + ".in", Out = s + ".out";  
13.     freopen(In.c\_str(), "r", stdin);  
14.     freopen(Out.c\_str(), "w", stdout);  
15. \}  
16.   
17. int f\[2010\]\[3\]\[9\]\[715\], n;//第一维当前处理人数，第二维运行方向，第三维楼层（0~8），第四维当前装载状态   
18. map<vector<int>, int> M;  
19. vector<int> load\[715\];  
20. pair<int, int> p\[2010\];  
21. bool cmp(int a, int b) \{  
22.     return a > b;  
23. \}  
24. int dfs(int cur, int op, int fl, int key) \{  
25.     if (cur == n + 1 && key == 0)  
26.         return 0;  
27.     if (fl == -1 || fl == 9)  
28.         return (int)1e9;  
29.     if (f\[cur\]\[op\]\[fl\]\[key\])  
30.         return f\[cur\]\[op\]\[fl\]\[key\];  
31.     int &ans = f\[cur\]\[op\]\[fl\]\[key\];  
32.     vector<int> tmp = load\[key\];  
33.     int lv = 0;  
34.     for (int i = 0; i < (int)tmp.size(); ++i)  
35.         if (tmp\[i\] == fl + 1)  
36.             tmp\[i\]= 0, ++lv;  
37.     if (lv) \{ //先下完   
38.         sort(tmp.begin(), tmp.end(), cmp);  
39.         return dfs(cur, 0, fl, M\[tmp\]) + lv;  
40.     \}  
41.     if (cur <= n && p\[cur\].st == fl + 1 && tmp\[3\] == 0) \{ //再来上人   
42.         tmp\[3\] = p\[cur\].dst;  
43.         sort(tmp.begin(), tmp.end(), cmp);  
44.         return ans = dfs(cur + 1, 0, fl, M\[tmp\]) + 1;  
45.     \}  
46.     //接下来是啥也没拉到的情况   
47.     if (op == 0)  //停着就上下动动   
48.         return ans = min(dfs(cur, 1, fl + 1, key), dfs(cur, 2, fl - 1, key)) + 1;  
49.     else if (op == 1) //继续往上   
50.         return ans = dfs(cur, 1, fl + 1, key) + 1;  
51.     else   
52.         return ans = dfs(cur, 2, fl - 1, key) + 1;  
53.       
54. \}  
55. int main() \{  
56.     open\_file("elevator");  
57.     ios::sync\_with\_stdio(0);  
58.     int cnt = -1;  
59.     for (int i = 0; i <= 9; ++i) // 降序排列   
60.         for (int j = 0; j <= i; ++j)  
61.             for (int k = 0; k <= j; ++k)  
62.                 for (int h = 0; h <= k; ++h) \{  
63.                     load\[++cnt\].push\_back(i);  
64.                     load\[cnt\].push\_back(j);  
65.                     load\[cnt\].push\_back(k);  
66.                     load\[cnt\].push\_back(h);  
67.                     M\[load\[cnt\]\] = cnt;  
68. //                  puts("%");   
69.                 \}  
70. //  cout << cnt;//最多715种状态   
71.     cin >> n;  
72.     for (int i = 1; i <= n; ++i)  
73.         cin >> p\[i\].st >> p\[i\].dst;  
74.     cout << dfs(1, 1, 0, 0) << endl;  
75.     return 0;  
76. \}

我感觉这题只能搜索，因为不知道电梯会在哪里停下，递推转移可能会很麻烦。（欢迎推翻这个flag）

转载于:https://www.cnblogs.com/TY02/p/11198649.html