Description：

一个 $9$ 层的楼和一个可以装四个人的电梯，每个人有所在楼层和想去楼层，进出电梯和电梯移动一层花费一秒，要求进电梯的顺序必须是原顺序，问所有人都到达的最短时间。

$1\le n \le 2000$

Solution：

楼层数很少，所以可以暴力记录电梯里每个人想去哪个楼层，按进电梯的顺序划分阶段，设 $f[i][p][t1][t2][t3][t4]$ 表示第 $i$ 个人刚上电梯，电梯在楼层 $p$ ，四个人分别想去 $t1,t2,t3,t4$ 的最短时间，暴力转移就能过，一个小剪枝是如果电梯坐满了，那上一个位置一定是某个人的出发位置，不过我没剪， $DP$ $n+1$ 轮保证所有人下电梯，时间复杂度 $2000\times 9^5$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 2010

int f[2][10][10][10][10][10];

int fr[MAXN],to[MAXN];

inline void getmin(int &a,int b){if(b < a)a = b;return;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d",&fr[i],&to[i]);

	memset(f,0x3f,sizeof(f));

	int cur = 0;

	f[cur][1][0][0][0][0] = 0;

	for(int i = 1;i <= n + 1;++i)

	{

		cur = cur ^ 1;

		memset(f[cur],0x3f,sizeof(f[cur]));

		for(int p = 1;p <= 9;++p)

		{

			for(int to1 = 1;to1 <= 9;++to1)

			{

				for(int to2 = 1;to2 <= 9;++to2)

				{

					for(int to3 = 1;to3 <= 9;++to3)

					{

						for(int to4 = 1;to4 <= 9;++to4)

						{

							if(f[cur ^ 1][p][to1][to2][to3][to4] >= 0x3f3f3f3f)continue;

							getmin(f[cur ^ 1][to1][to2][to3][to4][0],f[cur ^ 1][p][to1][to2][to3][to4] + abs(p - to1) + 1);

							getmin(f[cur ^ 1][to2][to1][to3][to4][0],f[cur ^ 1][p][to1][to2][to3][to4] + abs(p - to2) + 1);

							getmin(f[cur ^ 1][to3][to1][to2][to4][0],f[cur ^ 1][p][to1][to2][to3][to4] + abs(p - to3) + 1);

							getmin(f[cur ^ 1][to4][to1][to2][to3][0],f[cur ^ 1][p][to1][to2][to3][to4] + abs(p - to4) + 1);

						}

					}

				}

			}

		}

		for(int p = 1;p <= 9;++p)

		{

			for(int to1 = 1;to1 <= 9;++to1)

			{

				for(int to2 = 1;to2 <= 9;++to2)

				{

					for(int to3 = 1;to3 <= 9;++to3)

					{

						getmin(f[cur][fr[i]][to1][to2][to3][to[i]],f[cur ^ 1][p][to1][to2][to3][0] + abs(fr[i] - p) + 1);

						getmin(f[cur ^ 1][to1][to2][to3][0][0],f[cur ^ 1][p][to1][to2][to3][0] + abs(to1 - p) + 1);

						getmin(f[cur ^ 1][to2][to1][to3][0][0],f[cur ^ 1][p][to1][to2][to3][0] + abs(to2 - p) + 1);

						getmin(f[cur ^ 1][to3][to1][to2][0][0],f[cur ^ 1][p][to1][to2][to3][0] + abs(to3 - p) + 1);

					}

				}

			}

		}

		for(int p = 1;p <= 9;++p)

		{

			for(int to1 = 1;to1 <= 9;++to1)

			{

				for(int to2 = 1;to2 <= 9;++to2)

				{

					getmin(f[cur][fr[i]][to1][to2][to[i]][0],f[cur ^ 1][p][to1][to2][0][0] + abs(fr[i] - p) + 1);

					getmin(f[cur ^ 1][to1][to2][0][0][0],f[cur ^ 1][p][to1][to2][0][0] + abs(to1 - p) + 1);

					getmin(f[cur ^ 1][to2][to1][0][0][0],f[cur ^ 1][p][to1][to2][0][0] + abs(to2 - p) + 1);

				}

			}

		}

		for(int p = 1;p <= 9;++p)

		{

			for(int to1 = 1;to1 <= 9;++to1)

			{

				getmin(f[cur][fr[i]][to1][to[i]][0][0],f[cur ^ 1][p][to1][0][0][0] + abs(fr[i] - p) + 1);

				getmin(f[cur ^ 1][to1][0][0][0][0],f[cur ^ 1][p][to1][0][0][0] + abs(to1 - p) + 1);

			}

		}

		for(int p = 1;p <= 9;++p)

		{

			getmin(f[cur][fr[i]][to[i]][0][0][0],f[cur ^ 1][p][0][0][0][0] + abs(fr[i] - p) + 1);

		}

	}

	int ans = 0x3f3f3f3f;

	for(int i = 1;i <= 9;++i)

	{

		ans = min(ans,f[cur ^ 1][i][0][0][0][0]);

	}

	cout << ans << endl;

	return 0;

}