Codeforces Round 637

發表於 更新於 分類於 ， Disqus： 文章字數： 567 所需閱讀時間 ≈ 2 分鐘
C(入门bfs)

C

https://codeforces.com/contest/1340/problem/C

状态设计

应该算bfs+dp?

状态设计 dist[第i个检查点][剩余步数j] = 到达的最小轮数 或 不可达

转移从数轴上看，只有左右关系相邻的两个点能在dist中转换，每个点最多被更新一次。

所以 O(nm)时间空间

注意的是 不能跨过g，每次转移前是j<g,转以后的j<=g

Code

托爷代码：https://codeforces.com/contest/1340/submission/77808028

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

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const double pi = acos(-1.0);

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> d(m);
  for (int i = 0; i < m; i++) {
    cin >> d[i];
  }
  sort(d.begin(), d.end());
  int g, r;
  cin >> g >> r;
  // dist[0->m-1][0->g] = -1; 不可达
  // dist[第i个停靠点][还要走j步为g的整数倍] = 最小的完整轮数
  vector<vector<int>> dist(m, vector<int>(g + 1, -1));
  dist[0][g] = 0; // 可达的轮数为0
  vector<pair<int, int>> que;
  que.emplace_back(0, g);
  while (!que.empty()) {
    // 步数少于等于g的广搜
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b].first; // 位置
      int j = que[b].second; // 剩余步数
      if (i > 0) { //
        int go = d[i] - d[i - 1];
        if (j >= go) {
          if (dist[i - 1][j - go] == -1) {
            que.emplace_back(i - 1, j - go);
            dist[i - 1][j - go] = dist[i][j];
          }
        }
      }
      if (i < m - 1) {
        int go = d[i + 1] - d[i];
        if (j >= go) {
          if (dist[i + 1][j - go] == -1) {
            que.emplace_back(i + 1, j - go);
            dist[i + 1][j - go] = dist[i][j];
          }
        }
      }
    }
    vector<pair<int, int>> new_que;
    // 利用g表示 上一层节点，0表示新走到的节点， 产生新的一层
    for (int b = 0; b < (int) que.size(); b++) {
      int j = que[b].second;
      if (j == 0) { // 新走道德合法点
        int i = que[b].first;
        if (dist[i][g] == -1) {
          dist[i][g] = dist[i][0] + 1; // 轮次+1
          new_que.emplace_back(i, g);
        }
      }
    }
    swap(que, new_que);
  }
  const long long inf = (long long) 1e18;
  long long ans = inf;
  for (int i = 0; i <= g; i++) {
    if (dist[m - 1][i] != -1) { // 可达到 最后一个点一定是终点
      long long cur = (long long) dist[m - 1][i] * (g + r) + (g - i); //计算总时间
      ans = min(ans, cur);
    }
  }
  cout << (ans == inf ? -1 : ans) << '\n';
  return 0;
}

总结

还真是个大水题 放在1C

自己也在想dp，状态，还有dijs,看推有人还真的过了。