Codeforces 704B Ant Man

链接

传送门

题意

\(n\)个点,每个点有\(x_i\)\(a_i\)\(b_i\)\(c_i\)\(d_i\),五个值,从\(i\)点到\(j\)点移动的代价为:

  • \(i < j\)时,\(|x_i - x_j| + c_i + b_j\)
  • \(i > j\)时,\(|x_i - x_j| + d_i + a_j\)

给出起点\(s\)终点\(e\),从\(s\)\(e\)的哈密顿道路的最小代价。

思路

状态\(dp[i][j][k][l]\)表示前\(i\)个点的导出子图中有\(j\)个连通分量可以接任意起点和终点,有\(k\)条的起点为\(s\)可以接任意终点,有\(l\)条终点是\(e\)可以接任意起点时的最小代价。其中\(k\)\(l\)最大为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL inf = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 5010;
int x[maxn], a[maxn], b[maxn], c[maxn], d[maxn];
LL dp[2][maxn][2][2];

inline void Set(LL& a, LL b) {
if (a > b) {
a = b;
}
}

int main() {
int n, s, e;
scanf("%d%d%d", &n, &s, &e);
for (int i = 1; i <= n; ++i) {
scanf("%d", &x[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &b[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &c[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &d[i]);
}
memset(dp[0], 0x3f, sizeof dp[0]);
dp[0][0][0][0] = 0;
for (int p = 1; p <= n; ++p) {
int i = p & 1;
LL A = a[p] + x[p], B = b[p] - x[p];
LL C = c[p] + x[p], D = d[p] - x[p];
memset(dp[i], 0x3f, sizeof dp[i]);
for (int j = min(p, n - p); j >= 0; --j) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 2; ++l) {
LL& v = dp[1 - i][j][k][l];
if (v == inf) {
continue;
}
if (p == n) {
if (p == s) {
Set(dp[i][0][0][0], v + C);
} else if (p == e) {
Set(dp[i][0][0][0], v + A);
} else {
Set(dp[i][0][0][0], v + A + C);
}
} else {
if (p == s) {
if (j > 0) {
Set(dp[i][j - 1][1][l], v + C);
}
Set(dp[i][j][1][l], v + D);
} else if (p == e) {
if (j > 0) {
Set(dp[i][j - 1][k][1], v + A);
}
Set(dp[i][j][k][1], v + B);
} else {
Set(dp[i][j + 1][k][l], v + B + D);
if (j > 0) {
Set(dp[i][j][k][l], v + min(A + D, B + C));
if (j > 1 || k > 0 || l > 0) {
Set(dp[i][j - 1][k][l], v + A + C);
}
} else {
if (k > 0) {
Set(dp[i][j][k][l], v + A + D);
}
if (l > 0) {
Set(dp[i][j][k][l], v + B + C);
}
}
}
}
}
}
}
}
printf("%I64d\n", dp[n & 1][0][0][0]);
return 0;
}