Codeforces 704B Ant Man

发表于 分类于 Disqus：

链接

传送门

题意

有\(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;
}
相关文章