SP703 SERVICE – Mobile Service

CH5102/SP703

Problem

​ 线性DP状态化简好题

​ 根据题意，我们可以设已经完成了 i - 1 个请求现在转移到完成第 i 个为状态，我们发现，如果仅仅只知道完成了请求而不知道三个员工的位置是无法计算代价的，所以不妨再设 x, y, z 为三个员工的状态。

​ 此时我们有：

​ 设 f[i,x,y,z] 表示完成了前 i 个请求三个员工分别在 x,y,z 的最小代价

​ 观察数据范围，200^3 * 1000 的数据范围是要T掉的，所以继续考虑优化

​ 我们考虑，总有一个员工应该在 p_i 的位置，那么我们只需要知道其他两个员工的位置即可，不妨直接设其他两个员工在 x, y , 所以状态转变成:

​ 设 f[i,x,y] 表示完成了前 i 个请求时一定有一个员工在 p_i ，其他两个员工分别在 x,y 的位置时的最小代价

​ 可以很顺利地写出方程：

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

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

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

​ 起始位置：p_0 = 3， 初始值：f[0,1,2] = 0，目标：
min(f[n][?][?])
​ 还要注意判断位置的合法性

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1000 + 5;
const int inf = 0x7f; 

int n, m;
int a[210][210], p[SIZE], f[SIZE][210][210];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    int t = read();
    while (t--)
    {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        a[i][j] = read();
    for (int i = 1; i <= m; i++)
        p[i] = read();
    memset(f, 0x7f, sizeof(f));
    f[0][1][2] = 0, p[0] = 3;
    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];
            if (x == z || y == z || x == y) continue;
            if (x != p[i + 1] && y != p[i + 1])
            f[i + 1][x][y] = std::min(f[i + 1][x][y], f[i][x][y] + a[z][p[i + 1]]);
            if (z != p[i + 1] && x != p[i + 1])
            f[i + 1][x][z] = std::min(f[i + 1][x][z], f[i][x][y] + a[y][p[i + 1]]);
            if (y != p[i + 1] && z != p[i + 1])
            f[i + 1][y][z] = std::min(f[i + 1][y][z], f[i][x][y] + a[x][p[i + 1]]);
        }
    int ans = 0x7f7f7f7f;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        ans = std::min(ans, f[m][i][j]);
    printf("%d\n", ans);
    }
    return 0;
}