移动服务（f[i] [j] [k],这三个人，位置为a[i],j,k的最小价值）

题意

给出点之间到达价值，使用3个人处理一个序列，f[i] [j] [k],这三个人，每次处理序列中一个值，三个人中一个要到这个点。三个人不能重复到达一个点。

思路

状态表示：f[i] [a] [b] [c]:表示：处理到第i个序列中的数，这三个人位置分别在a，b，c时的最小花费。

这个状态有三种去向：

a去下一个位置
b去下一个位置
c去下一个位置

像重复覆盖问题一样，拿前面的状态更新后面的状态。注意这三个点不能一样。

状态初始化的时候，我们可以定义f[0] [1] [2]=0,a[0]=3,然后下一步就走到初始位置了

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 210, M = 1010, INF = 0x3f3f3f3f;

int n, m;

int w[N][N];

int f[M][N][N];

int p[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 ++ ) scanf("%d", &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 || x == z || y == 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 || x == z || y == z) continue;

            res = min(res, f[m][x][y]);

        }

    printf("%d\n", res);

    return 0;

}

移动服务（f[i] [j] [k],这三个人，位置为a[i],j,k的最小价值）的相关教程结束。