acwing 274. 移动服务

2022-07-17 11:49:42

题面：

一个公司有三个移动服务员，最初分别在位置1，2，3处。

如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。

某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。

从 p 到 q 移动一个员工，需要花费 c(p,q)。

这个函数不一定对称，但保证 c(p,p)=0。

给出N个请求，请求发生的位置分别为

公司必须按顺序依次满足所有请求，目标是最小化公司花费，请你帮忙计算这个最小花费。

输入格式

第1行有两个整数L,N，其中L是位置数量，N是请求数量，每个位置从1到L编号。

第2至L+1行每行包含L个非负整数，第i+1行的第j个数表示c(i,j) ，并且它小于2000。

最后一行包含N个整数，是请求列表。

一开始三个服务员分别在位置1，2，3。

输出格式

输出一个整数M，表示最小花费。

数据范围

输入样例：

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1

输出样例：

题解：

(DP,线性DP) O(NL2)O(NL2)
状态表示：

f[i][x][y]表示已经处理完前i个请求，且三个服务员分别在p[i], x, y的所有方案的集合；
f[i][x][y]的值是集合中所有方案的花费的最小值；
状态计算：
这里状态之间的拓扑关系比较特殊，f[i][x][y]所依赖的状态枚举起来不太方便，但f[i][x][y]被依赖的很容易枚举（即第二种依赖），只有3类：

位于p[i]的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][y] = f[i][x][y] + w[p[i]][p[i + 1]];
位于x的服务员出发前往p[i + 1]，此时状态变成f[i + 1][p[i]][y] = f[i][x][y] + w[x][p[i + 1]];
位于y的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][p[i]] = f[i][x][y] + w[y][p[i + 1]];
最终答案从f[m][1...n][1...n]取最小值即可。

时间复杂度
共有 NL2NL2 个状态，计算每个状态需要 O(1)O(1) 的计算量，因此总时间复杂度是 O(NL2)O(NL2)。

代码实现：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
int f[1010][210][210];
int p[1010];
int w[210][210];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      scanf("%d",&w[i][j]);
      for(int i=1;i<=m;i++)cin>>p[i];
      p[0]=3;
      memset(f,0x3f,sizeof f);
      f[0][1][2]=0;
      for(int i=0;i<m;i++)
       for(int x=1;x<=n;x++)
        for(int y=1;y<=n;y++)
        {
            int z=p[i],v=f[i][x][y];
            if(x==y||y==z||x==z)continue;
            int u=p[i+1];
            f[i+1][x][y]=min(f[i+1][x][y],v+w[z][u]);
            f[i+1][z][y]=min(f[i+1][z][y],v+w[x][u]);
            f[i+1][x][z]=min(f[i+1][x][z],v+w[y][u]);
        }
        int res=inf;
        for(int x=1;x<=n;x++)
         for(int y=1;y<=n;y++)
         {
             int z=p[m];
             if(x==y||y==z||x==z)continue;
             res=min(res,f[m][x][y]);
         }
         printf("%d\n",res);
    return 0;
}