题解：P7685 [CEOI 2005] Mobile Service
Soh_paramEEMS
·
·
题解
本题解把 SP703 和洛谷 P7685 写在一起，便于循序渐进地做题。
题意
一个公司有三个移动服务员。如果某个地方有一个请求，某个服务员必须赶到那个地方去（那个地方没有其他服务员），某一时刻只有一个服务员能移动。被请求后，他才能移动，不允许在同样的位置出现两个服务员。从 p 到 q 移动一个服务员，需要花费 c(p,q)，c(p,p)=0。公司必须满足所有的请求，目标是最小化公司花费，并输出每次请求提供服务的服务员编号 1,2,3。
共有 m 个地方，n 个请求。
SP703：多测组数$T$，大小不详，较小；无输出编号需求。
洛谷P7685：$3\le m\le 200,1\le n\le 1000,64\rm MB$。
下文将提供洛谷 P7685 数据要求的题解，其他数据范围敬请自行修改。
## 思路
最朴素的状态设法，设 $f_{i,x,y,z}$ 表示完成第 $i$ 个请求后，三个服务员各自在 $x,y,z$。
但是看到空间限制无比的小，因此状态下标那么多，肯定开不下。
我们发现，每个请求之后，三个服务员中，肯定有一个服务员在请求位置 $a_i$，因此我们尝试从这里下手，缩减状态。
令 $f_{i,x,y}$ 表示，三个服务员一个去到了 $a_i$ ，剩下两个在位置 $x,y$ 的最小代价，不妨令 $z=a_{i-1}$ ，那么显然的有：
$$f_{i,x,y}=\min \{f_{i-1,x,y}+c(z,a_i)\}$$
$$f_{i,x,z}=\min \{f_{i-1,x,y}+c(y,a_i)\}$$
$$f_{i,y,z}=\min \{f_{i-1,x,y}+c(x,a_i)\}$$
记得判断三个位置相互不同。
还想缩减空间，那就滚动数组吧。
```cpp
memset(f,inf,sizeof(f));
f[0][1][2]=0;
a[0]=3;
for(int i=1;i<=n;i++)
{
ll now=i&1,las=now^1;
memset(f[now],inf,sizeof(f[now]));
for(int x=1;x<=m;x++)
{
for(int y=1;y<=m;y++)
{
ll z=a[i-1];
if(x==y||y==z||z==x)continue;
if(!(x==y||y==a[i]||a[i]==x))f[now][x][y]=min(f[now][x][y],f[las][x][y]+c[z][a[i]]);
if(!(x==z||z==a[i]||a[i]==x))f[now][x][z]=min(f[now][x][z],f[las][x][y]+c[y][a[i]]);
if(!(y==z||z==a[i]||a[i]==y))f[now][y][z]=min(f[now][y][z],f[las][x][y]+c[x][a[i]]);
}
}
}
```
不过写完代码之后，发现交在 SP703 被无脑卡常。我的原因是对 $x,y$ 两状态循环的时候，两个全枚举了 $1\sim n$，那么尝试缩减，通过保证两个状态 $x<y$ 可以实现缩减状态枚举量（虽然只是除以二）。具体实现见代码。
## 代码（SP703）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M=202,N=1002,inf=0x3f3f3f3f;
int T,m,n,c[M][M],a[N];
ll f[2][M][M];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
scanf("%d",&c[i][j]);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(f,inf,sizeof(f));
f[0][1][2]=0;
a[0]=3;
for(int i=1;i<=n;i++)
{
int now=i&1,las=now^1;
memset(f[now],inf,sizeof(f[now]));
for(int x=1;x<=m;x++)
{
for(int y=x+1;y<=m;y++)
{
int z=a[i-1];
if(x==y||y==z||z==x)continue;
if(!(x==y||y==a[i]||a[i]==x))f[now][x][y]=min(f[now][x][y],f[las][x][y]+c[z][a[i]]);
if(!(x==z||z==a[i]||a[i]==x))f[now][min(x,z)][max(x,z)]=min(f[now][min(x,z)][max(x,z)],f[las][x][y]+c[y][a[i]]);
if(!(y==z||z==a[i]||a[i]==y))f[now][min(y,z)][max(y,z)]=min(f[now][min(y,z)][max(y,z)],f[las][x][y]+c[x][a[i]]);
}
}
}
ll ret=inf;
for(int x=1;x<=m;x++)
{
for(int y=1;y<=m;y++)
{
if(x==y)continue;
ret=min(ret,f[n&1][x][y]);
}
}
printf("%lld\n",ret);
}
return 0;
}
```
那么怎么才能找到前往服务的服务员编号呢？那就要在 dp 的时候作处理了。
我们记 $pos_{i,x,y}$ 表示，遍历到第 $i$ 个请求时，“处理请求 $a_i$ 的并非在位置 $x,y$ 的服务员”这一情况是否改变，如果不改变则为 $0$，否则就是前往 $a_i$ 的服务员的前继位置。
找最小代价的时候，把最终最小代价所处的状态 ${\rm ans}=f_{n,x,y}$ 的 $x,y$ 记为 $minx=x,miny=y$ ，即其中一个服务员处理完请求 $a_n$ 之后，其他两个服务员所在的位置。
令 $X_i,Y_i$ 表示处理第 $i$ 个请求时，其中一个服务员处理请求 $a_i$ ，其他两个服务员所在的位置。那就可以考 $\rm pos$ 数组反推了：
初始状态 $X_n=minx,Y_n=miny$，考虑倒序枚举 $i:n\rightarrow1$，每次更新$minx,miny$ 从而更新 $X_i,Y_i$。
如果上文的“情况”不改变，那么 $X_i,Y_i$ 相应不变，不更新 $minx,miny$；否则将等于 $a_{i-1}$ 的 $minx$ 或者 $miny$ 置为 $pos_{i,X_i,Y_i}$。
```cpp
for(int i=n;i>=1;i--)
{
x[i]=minx,y[i]=miny;
int tem=pos[i][x[i]][y[i]];
if(tem)
{
if(minx==a[i-1])minx=tem;
else miny=tem;
}
}
```
得到了 $X,Y$ 数组，就可以输出答案了。由于编号 $1\sim 3$ 有一个很好的性质，就是和为 $6$，知道了其中两个编号，那么另外一个就是唯一的。而我们正要通过 $X,Y$ 数组更新对应编号：即记 $A,B$ 表示当前没有前往请求 $a_i$ 的服务员编号，初始不妨设为 $A=1,B=2$ （反正是 Special Judge）。
具体及细节见代码。
## 代码（洛谷P7685）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uc unsigned char
const int M=202,N=1002,inf=0x3f3f3f3f;
int m,n,c[M][M],a[N];
ll f[2][M][M];
int x[N],y[N];
uc pos[N][M][M];
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
scanf("%d",&c[i][j]);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(f,inf,sizeof(f));
f[0][1][2]=0;
a[0]=3;
x[0]=1,y[0]=2;
for(int i=1;i<=n;i++)
{
int now=i&1,las=now^1;
memset(f[now],inf,sizeof(f[now]));
for(int x=1;x<=m;x++)
{
for(int y=1;y<=m;y++)
{
int z=a[i-1];
if(x==y)continue;
if(!(x==a[i]||y==a[i]))
{
ll tem=f[las][x][y]+c[z][a[i]];
if(tem<f[now][x][y])
{
f[now][x][y]=tem;
pos[i][x][y]=0;
}
}
if(!(x==a[i]||z==a[i]))
{
ll tem=f[las][x][y]+c[y][a[i]];
if(tem<f[now][x][z])
{
f[now][x][z]=tem;
pos[i][x][z]=y;
}
}
if(!(y==a[i]||z==a[i]))
{
ll tem=f[las][x][y]+c[x][a[i]];
if(tem<f[now][z][y])//y上下对应
{
f[now][z][y]=tem;
pos[i][z][y]=x;
}
}
}
}
}
ll ret=inf;
int minx=0,miny=0,A=1,B=2;
for(int x=1;x<=m;x++)
{
for(int y=1;y<=m;y++)
{
if(f[n&1][x][y]<ret)
{
ret=f[n&1][x][y];
minx=x,miny=y;
}
}
}
printf("%lld\n",ret);
for(int i=n;i>=1;i--)
{
x[i]=minx,y[i]=miny;
int tem=pos[i][x[i]][y[i]];
if(tem)
{
if(minx==a[i-1])minx=tem;
else miny=tem;
}
}
for(int i=1;i<=n;i++)
{
if(x[i]==a[i-1])A=6-A-B;//不变即继承
else if(y[i]==a[i-1])B=6-A-B;
printf("%d ",6-A-B);
}
return 0;
}
```