题解 P4046 【[JSOI2010]快递服务】

这道题其实和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[2][205][205];
int c[205][205], p[1005];

int main()
{
    int l;
    scanf("%d", &l);
    for (int i = 1; i <= l;i++)
    {
        for (int j = 1; j <= l;j++)
        {
            int a;
            scanf("%d", &a);
            c[i][j] = a;
        }
    }
    int n = 0;
    while(scanf("%d", &p[++n])!=EOF);
    memset(f, 0x3f, sizeof(f));
    f[0][1][2] = 0;
    p[0] = 3;
    for (int i = 0; i < n;i++)
    {
        memset(f[i + 1 & 1], 0x3f, sizeof(f[i + 1 & 1]));
        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 & 1][p[i]][y] = min(f[i + 1 & 1][p[i]][y], f[i & 1][x][y] + c[x][p[i + 1]]);
                f[i + 1 & 1][x][p[i]] = min(f[i + 1 & 1][x][p[i]], f[i & 1][x][y] + c[y][p[i + 1]]);
                f[i + 1 & 1][x][y] = min(f[i + 1 & 1][x][y], f[i & 1][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++)
        {
            if(i==j||i==p[n]||j==p[n])
                continue;
            ans = min(ans, f[n & 1][i][j]);
        }    
    printf("%d", ans);
}