题意：
在一个9层的大楼内（大河内一*？），只有一台电梯，现在有N个人按顺序要乘电梯去他们想去的楼层，且不到达他们的目的地他们是不会下电梯的，要求每时每刻电梯内最多有4人，且上电梯的顺序必须严格按照人到达的顺序。但下电梯的顺序是任意的。每个人上、下电梯均需要1s，电梯移动一层也需要1s。现在求如何控制电梯，使得让所有人到达目的地的时间总和尽量小？
N≤2000N≤2000
分析：
据说这道题还有最短路做法。。。不过我没去研究，就写一下考场上的做法吧：
考虑到数据范围极其小，很容易想到状压DP，
DP[i][j][k]DP[i][j][k]表示前i个人已经上过电梯，现在电梯内的人目的地状态为j（4位10进制数，0表示没有人），电梯目前在k层。
粗略算一下复杂度：2000×104×10=2×1082000×104×10=2×108估计要炸。
考虑优化一维，很显然，如果电梯是满员，那么必然会直接找一个位置让人下电梯（不能再上人了），那么这种情况不需要特别写一个状态来保存，每次转移后满员时，直接枚举停的位置，让某个人下电梯，这样一来又转移到3个人的状态。所以复杂度为2000×103×10=2?1072000×103×10=2?107就没什么大问题了。
转移很暴力很简单，这里就不细说了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 2010
#define MAXM 10010
#define INF 0x3FFFFFFF
using namespace std;
typedef long long ll;
int n;
int dp[MAXN][MAXM];
int st[MAXN],ed[MAXN];
int pos[5],now;
void get_num(int x){now=x%10;pos[0]=x/10%10;pos[1]=x/100%10;pos[2]=x/1000;
}
int get_sum(){return pos[2]*1000+pos[1]*100+pos[0]*10+now;}
int main(){SF("%d",&n);for(int i=1;i<=n;i++)SF("%d%d",&st[i],&ed[i]);memset(dp,0x3f3f3f3f,sizeof dp);dp[0][1]=0;for(int i=0;i<=n;i++)for(int j=9999;j>0;j--){if(dp[i][j]==0x3f3f3f3f)continue;get_num(j);int now1=now,p1;for(int k=0;k<3;k++)if(pos[k]){now=pos[k];p1=pos[k];pos[k]=0;int nxt=get_sum();dp[i][nxt]=min(dp[i][nxt],dp[i][j]+abs(now1-p1)+1);get_num(j);}if(i==n)continue;for(int k=0;k<3;k++){if(pos[k]){now=pos[k];p1=pos[k];pos[k]=ed[i+1];int nxt=get_sum();dp[i+1][nxt]=min(dp[i+1][nxt],dp[i][j]+abs(now1-st[i+1])+1+abs(st[i+1]-now)+1);get_num(j);}else{now=st[i+1];p1=pos[k];pos[k]=ed[i+1];int nxt=get_sum();dp[i+1][nxt]=min(dp[i+1][nxt],dp[i][j]+abs(now1-now)+1);get_num(j);}}now=ed[i+1];int nxt=get_sum();dp[i+1][nxt]=min(dp[i+1][nxt],dp[i][j]+abs(now1-st[i+1])+1+abs(st[i+1]-ed[i+1])+1);}int res=INF;for(int i=1;i<=9;i++)res=min(res,dp[n][i]);PF("%d",res);
}