非常好的题！和spoj 的 Mobile Service有点相似，用记忆化搜索很容易解决
看了网上的题解，也是减掉一维，刚好可以开下数组 https://blog.lucien.ink/archives/224/
#include<bits/stdc++.h>
using namespace std;
#define maxn 2005
int n,A[maxn],B[maxn];
int dp[maxn][][][][]; //状态：准备去拉第i个人，当前在cur楼，另外三个人的目标楼层是abc
int dfs(int i,int cur,int a,int b,int c){
if(dp[i][cur][a][b][c]!=-)
return dp[i][cur][a][b][c];
int res=0x3f3f3f3f;
if(i>n){//终止状态，只要把abc送到终点即可
if(!a && !b && !c)res=;
if(a!=)res=min(res,dfs(i,a,,b,c)+abs(cur-a)+);//送到a
if(b!=)res=min(res,dfs(i,b,a,,c)+abs(cur-b)+);//送到b
if(c!=)res=min(res,dfs(i,c,a,b,)+abs(cur-c)+);//送到c
return dp[i][cur][a][b][c]=res;
}
//先放下abc的决策
if(a)res=min(res,dfs(i,a,,b,c)+abs(cur-a)+);
if(b)res=min(res,dfs(i,b,a,,c)+abs(cur-b)+);
if(c)res=min(res,dfs(i,c,a,b,)+abs(cur-c)+); //准备去拉一个人的决策:先去把i接上电梯
if(a&&b&&c){//电梯全满，再拉一个人需要先放下一个人
res=min(res,dfs(i+,B[i],a,b,c)+abs(cur-A[i])+abs(A[i]-B[i])+);
res=min(res,dfs(i+,a,B[i],b,c)+abs(cur-A[i])+abs(A[i]-a)+);
res=min(res,dfs(i+,b,a,B[i],c)+abs(cur-A[i])+abs(A[i]-b)+);
res=min(res,dfs(i+,c,a,b,B[i])+abs(cur-A[i])+abs(A[i]-c)+);
}
else {//先去接i，再拉一个人
if(!a)res=min(res,dfs(i+,A[i],B[i],b,c)+abs(cur-A[i])+);
else if(!b)res=min(res,dfs(i+,A[i],a,B[i],c)+abs(cur-A[i])+);
else if(!c)res=min(res,dfs(i+,A[i],a,b,B[i])+abs(cur-A[i])+);
}
return dp[i][cur][a][b][c]=res;
} int main(){
memset(dp,-,sizeof dp);
cin>>n;
for(int i=;i<=n;i++)cin>>A[i]>>B[i];
cout<<dfs(,,,,)<<'\n';
}
此外是滚动数组的版本（没有降维复杂度比较高）
#include<bits/stdc++.h>
using namespace std;
#define maxn 2005 int n,a[maxn],b[maxn],dp[][][][][][]; void calc(int &a,int b){
int tmp=min(a,b);
a=tmp;
} int main(){
cin>>n;
for(int i=;i<=n;i++)cin>>a[i]>>b[i];
memset(dp,0x3f,sizeof dp); int cur=;
dp[cur][][][][][]=*n;//开始停在1楼,因为n个人总共上下2*n次，所以直接加上这个值
for(int i=;i<=n;i++){//去接第i+1个人
for(int x=;x>=;x--)//这里必须逆序，因为把电梯里的人放下时的目标状态是dp[cur][][0][0][0][0],即消除掉后效性
for(int y=;y>=;y--)
for(int z=;z>=;z--)
for(int w=;w>=;w--)
for(int f=;f<=;f++){
int now=dp[cur][f][x][y][z][w];
if(now==0x3f3f3f3f)continue;
if(x== && i<n)//把第i+1个人放在位置x,更新状态到下一步
calc(dp[cur^][a[i+]][b[i+]][y][z][w],now+abs(f-a[i+]));
else if(x)//不接人把电梯里的人送到目的地
calc(dp[cur][x][][y][z][w],now+abs(f-x));
if(y== && i<n)
calc(dp[cur^][a[i+]][x][b[i+]][z][w],now+abs(f-a[i+]));
else if(y)
calc(dp[cur][y][x][][z][w],now+abs(f-y));
if(z== && i<n)
calc(dp[cur^][a[i+]][x][y][b[i+]][w],now+abs(f-a[i+]));
else if(z)
calc(dp[cur][z][x][y][][w],now+abs(f-z));
if(w== && i<n)
calc(dp[cur^][a[i+]][x][y][z][b[i+]],now+abs(f-a[i+]));
else if(w)
calc(dp[cur][w][x][y][z][],now+abs(f-w));
}
if(i<n){
memset(dp[cur],0x3f,sizeof dp[cur]);
cur^=;
}
}
int ans=0x3f3f3f3f;
for(int i=;i<=;i++)
ans=min(ans,dp[cur][i][][][][]);
cout<<ans<<'\n';
}