非常好的题!和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';
}

最新文章

  1. pt-mext
  2. 神秘的 shadow-dom 浅析
  3. SQL Server 2012日志文件误删除数据库质疑后的相关恢复
  4. 图灵机器人(问答机器人)API调用示例
  5. super用法
  6. Codevs 2611 观光旅游
  7. firefox同步ajax请求报错的问题 A parameter or an operation is not supported by the underlying object
  8. Python中的迭代器和生成器
  9. Python网络编程——处理套接字错误
  10. 微信小程序之自定义toast弹窗
  11. linux下sort命令详解大全
  12. java 一次CPU占用过高问题的排查及解决
  13. Maven配置阿里云镜像仓库
  14. java位运算(操作)的使用
  15. python模块os
  16. linux内核netfilter模块分析之:HOOKs点的注册及调用
  17. 算法day02
  18. 复选框checkbox样式修改
  19. 网卡流量监控脚本 ( Python )
  20. 【scala】IO

热门文章

  1. 查看crontab执行记录
  2. go变量和声明
  3. mockjs 使用以及反向校验
  4. Arduino与无源蜂鸣器
  5. 如何扫描统计全国Telnet默认口令
  6. JAVA调用R脚本 windwos路径下
  7. 24、echarts做报表
  8. 如何解决Unsupported major.minor version 52.0问题?
  9. 1、Appium Desktop介绍
  10. HDU 6574 Rng