一个公司有三个移动服务员,最初分别在位置1,2,3处。 如果某个位置(用一个整数表示)有一个请求,那么公司必须指派某名员工赶到那个地方去。某一时刻只有一个员工能移动,且不允许在同样的位置出现两个员工。从 p 到 q 移动一个员工,需要花费 c(p,q)。这个函数不一定对称,但保证 c(p,p)=0。 给出N个请求,请求发生的位置分别为 $p_1 \sim p_N$ 。公司必须按顺序依次满足所有请求,目标是最小化公司花费,请你帮忙计算这个最小花费。 $N \leq 1000$,位置是1~200的整数。

输入描述:

第一行有两个整数L,N $(3 \leq L \leq 200, 1 \leq N \leq 1000)$。L是位置数;N是请求数。每个位置从1到L编号。 下L行每行包含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

输出样例:

5

题目分析

我们可以假设 f(i, x, y, z) 为 i 个请求的情况下, 三个员工分别在 x, y, z 时的最小服务花费。 易得状态转移方程:

  • f(i + 1, q, y, z) = f(i, x, y, z) + c(x, q)
  • f(i + 1, x, q, z) = f(i, x, y, z) + c(y, q)
  • f(i + 1, x, y, q) = f(i, x, y, z) + c(z, q)

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, M = 1010, INF = 0x7fffffff;

int l, n, q, c[N][N], dp[M][N][N][N], ans = INF;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> l >> n;
    for(int i = 1; i <= l; ++i)
        for(int j = 1; j <= l; ++j) cin >> c[i][j];
    memset(dp, 0x3f, sizeof dp);
    dp[0][1][2][3] = 0;
    for(int i = 0; i < n; ++i) {
        cin >> q;
        for(int w1 = 1; w1 <= l; ++w1) {
            for(int w2 = 1; w2 <= l; ++w2) {
                if(w2 == w1) continue;
                for(int w3 = 1; w3 <= l; ++w3) {
                    if(w3 == w1 || w3 == w2) continue;
                    dp[i + 1][q][w2][w3] = min(dp[i + 1][q][w2][w3], dp[i][w1][w2][w3] + c[w1][q]);
                    dp[i + 1][w1][q][w3] = min(dp[i + 1][w1][q][w3], dp[i][w1][w2][w3] + c[w2][q]);
                    dp[i + 1][w1][w2][q] = min(dp[i + 1][w1][w2][q], dp[i][w1][w2][w3] + c[w3][q]);
                    if(i + 1 == n)
                        ans = min(min(ans, dp[i + 1][w1][w2][q]),min(dp[i + 1][q][w2][w3], dp[i + 1][w1][q][w3]));
                }
            }    
        }
    }
    cout << ans;
    return 0;
}

但是很明显, 对于 dp[][][][], M N^3 = 1000 200^3 = 2e9。我们可以考虑去掉一维使用滚动数组优化空间。

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, M = 1010, INF = 0x7fffffff;

bool f;
int l, n, q, c[M][M], dp[2][N][N][N], ans = INF;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> l >> n;
    for(int i = 1; i <= l; ++i)
        for(int j = 1; j <= l; ++j) cin >> c[i][j];
    bool f;
    memset(dp, 0x3f, sizeof dp);
    dp[f][1][2][3] = 0;
    for(int i = 0; i < n; ++i) {
        cin >> q;
        for(int w1 = 1; w1 <= l; ++w1) {
            for(int w2 = 1; w2 <= l; ++w2) {
                if(w2 == w1) continue;
                for(int w3 = 1; w3 <= l; ++w3) {
                    if(w3 == w1 || w3 == w2) continue;
                    dp[!f][q][w2][w3] = min(dp[!f][q][w2][w3], dp[f][w1][w2][w3] + c[w1][q]);
                    dp[!f][w1][q][w3] = min(dp[!f][w1][q][w3], dp[f][w1][w2][w3] + c[w2][q]);
                    dp[!f][w1][w2][q] = min(dp[!f][w1][w2][q], dp[f][w1][w2][w3] + c[w3][q]);
                    if(i + 1 == n) ans = min(min(ans, dp[!f][w1][w2][q]), min(dp[!f][q][w2][w3], dp[!f][w1][q][w3]));
                }
            }    
        }
        memset(dp[f], 0x3f, sizeof dp[f]);
        f = !f;
    }
    cout << ans;
    return 0;
}

但是这样会 TLE。 我们继续思考,显然,在每次迭代的过程中, 一定有一个员工所在的位置是上一个请求的地址。那么我们考虑将 x, y, z 分别表示三个员工的位置优化为 x, y, p,即只使用 dp[i][x][y] 来表示在 i 个请求的情况下, 两个员工分别在 x, y 时(另一个在 p)的最小服务花费。

那么状态转移方程会出现相应的变化:

  • f(i + 1, p, y) = f(i, x, y) + c(x, q) (可以理解为先将位于 x 和 z 的服务员交换后再将z转到q)
  • f(i + 1, x, p) = f(i, x, y) + c(y, q)
  • f(i + 1, x, y) = f(i, x, y) + c(p, q)

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, M = 1e3 + 10, INF = 0x7fffffff;

int l, n, p[M], c[M][M], dp[M][N][N];
int work() {
    p[0] = 3;
    int ans = INF;
    memset(dp, 0x3f, sizeof dp);
    dp[0][1][2] = 0;
    for(int i = 0; i < n; ++i) {
        cin >> p[i + 1];
        for(int x = 1; x <= l; ++x) {
            for(int y = 1; y <= l; ++y) {
                if(x == y || x == p[i] || y == p[i]) continue;
                dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y] + c[p[i]][p[i + 1]]);
                dp[i + 1][p[i]][y] = min(dp[i + 1][p[i]][y], dp[i][x][y] + c[x][p[i + 1]]);
                dp[i + 1][x][p[i]] = min(dp[i + 1][x][p[i]], dp[i][x][y] + c[y][p[i + 1]]);
                if(i == n - 1)
                    ans = min(min(ans, dp[i + 1][x][y]), min(dp[i + 1][p[i]][y], dp[i + 1][x][p[i]]));
            }    
        }
    }
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> l >> n;
    for(int i = 1; i <= l; ++i) for(int j = 1; j <= l; ++j) cin >> c[i][j];
    cout << work();
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status