#动态规划#SP703 codevs 2182 1383 CH 5102 Mobile Service 移动服务

本文主要是介绍#动态规划#SP703 codevs 2182 1383 CH 5102 Mobile Service 移动服务，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

有三个移动服务员，最初分别在位置1，2，3处。
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。从 $p$ 到 $q$ 移动一个员工，需要花费 $c (p, q)$ 。求最小花费。

分析

用动态规划，但是普通的动态规划不仅时间超时，空间也无法满足，所以需要优化，可以发现员工应该在的位置其实是冗余，所以说可以优化为

f[x][i][j]=f[x][j][i]=min(f[x][i][j],f[x^1][i][j]+c[ls][y]);//从上一个点赶到这一个点f[x][ls][j]=f[x][j][ls]=min(f[x][j][ls],f[x^1][i][j]+c[i][y]);//从i点赶到这一个点f[x][i][ls]=f[x][ls][i]=min(f[x][i][ls],f[x^1][i][j]+c[j][y]);//从j点赶到这一个点

时间复杂度 $O(mn^2)$

代码

#include <cstdio>
#include <cstring>
int n,m,ls,y,f[2][201][201],c[201][201];
int in(){int ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
int min(int a,int b){return (a<b)?a:b;}
int main(){n=in(); m=in(); memset(f[0],127/3,sizeof(f[0]));for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) c[i][j]=in();ls=in(); int ans=f[0][0][0],x=0;f[0][1][2]=f[0][2][1]=c[3][ls]; //初始化f[0][1][3]=f[0][3][1]=c[2][ls];f[0][2][3]=f[0][3][2]=c[1][ls];while (--m){x^=1; memset(f[x],127/3,sizeof(f[x])); y=in();for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (i!=j&&i!=ls&&j!=ls)//动态规划（滚动数组）f[x][i][j]=f[x][j][i]=min(f[x][i][j],f[x^1][i][j]+c[ls][y]),f[x][ls][j]=f[x][j][ls]=min(f[x][j][ls],f[x^1][i][j]+c[i][y]),f[x][i][ls]=f[x][ls][i]=min(f[x][i][ls],f[x^1][i][j]+c[j][y]);ls=y;}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) ans=min(ans,f[x][i][j]);return !printf("%d",ans);
}