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