题解 SP703 【SERVICE - Mobile Service】

看到这到题,很容易想到一种定义状态的方式$f[i][x][y][z]$表示完成前$i$个请求,三个人的位置分别在$x,y,z$,但很明显如果这么定义会超空间,所以想办法减掉一位,因为完成请求必须要有一个人在请求发生的位置,那么,我们就可以用当前完成的第$i$个请求来推出其中一个人的位置,所一这个状态就可变成$f[i][x][y]$,b表示完成前$i$个请求时,其中两个人分别在$x,y$,接下来考虑怎么转移状态,如果我们从前面的状态来推当前的状态,需要考虑许多种情况,所以我们就用当前状态来更新下一个状态

---

然后是状态转移方程，因为有三个员工,那么我们可以考虑,

在当前请求的位置的人去

$f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + c[p[i]][p[i+1]])$

在$x$位置的员工去

$f[i + 1][p[i]][y] = min(f[i + 1][p[i]][y], f[i][x][y]+c[x][p[i + 1]])$

在$y$位置的员工去

$f[i + 1][x][p[i]] = min(f[i + 1][x][p[i]], f[i][x][y]+c[y][p[i + 1]])$

得出状态转移方程,这到题就基本解决了

附代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int f[1005][205][205];
int c[205][205], p[1005];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int l, n;
        scanf("%d%d", &l, &n);
        for (int i = 1; i <= l;i++)
        {
            for (int j = 1; j <= l;j++)
            {
                int a;
                scanf("%d", &a);
                c[i][j] = a;
            }
        }
        for (int i = 1; i <= n;i++)
            scanf("%d", &p[i]);
        memset(f, 0x3f, sizeof(f));
        f[0][1][2] = 0;
        p[0] = 3;//初始化
        for (int i = 0; i < n;i++)
        {
            for (int x = 1; x <= l;x++)
            {
                for (int y = 1; y <= l;y++)
                {
                    if(x==p[i]||x==y||y==p[i])
                        continue;
                    f[i + 1][p[i]][y] = min(f[i + 1][p[i]][y], f[i][x][y] + c[x][p[i + 1]]);
                    f[i + 1][x][p[i]] = min(f[i + 1][x][p[i]], f[i][x][y] + c[y][p[i + 1]]);
                    f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + c[p[i]][p[i + 1]]);//转移状态
                }
            }
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= l;i++)
            for (int j = 1; j <= l;j++)
                ans = min(ans, f[n][i][j]);//取最小
        printf("%d\n", ans);
    }
}