题目分析
我们可以假设 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;
}