Codeforces 677D Vanya and Treasure

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n \times m\)的矩阵，每个矩阵中的数字都在\([1,p]\)，保证每个数字出现至少一次，\(p\)只出现1次。从\((1,1)\)出发，依次经过含有\(1\)到\(p\)，求最短路。

思路

设\((i,j)\)包含的数字为\(x\)，一个显然的状态\(dp[i][j]\)表示经过了前\(x\)个数之后到\((i,j)\)点的最短路，可以从所有包含\(x-1\)的格子转移过来。设包含\(x\)的格子数为\(cnt[x]\)，每次转移的操作数为\(cnt[x]cnt[x-1]\)。但是直接这么做的复杂度最坏情况下达到了\(O(n^2m^2)\)并不能过。

所以我们加入暴力的方法，当\(cnt[x]cnt[x-1]>n*m\)时，直接用所有包含\(x-1\)的个子作为起点bfs，单次转移复杂度为\(O(nm)\)。

可以证明，最终复杂度为\(O(nm\sqrt{nm})\)。

复杂度证明：Codeforces Round #355 (Div. 2) Editorial

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <map>
#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int maxn = 305;

int d[maxn][maxn], dp[maxn][maxn];
queue<pii> q;
vector<pii> v[maxn * maxn];

int dis(const pii& a, const pii& b) {
  return abs(a.X - b.X) + abs(a.Y - b.Y);
}

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

bool cmp(const pii& p1, const pii& p2) {
  return dp[p1.X][p1.Y] < dp[p2.X][p2.Y];
}

int main() {
  int n, m, p, x;
  scanf("%d%d%d", &n, &m, &p);
  memset(dp, 0x3f, sizeof dp);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      scanf("%d", &x);
      v[x].push_back(make_pair(i, j));
      if (x == 1) {
        dp[i][j] = i + j - 2;
      }
    }
  }
  for (int i = 2; i <= p; ++i) {
    if (v[i - 1].size() * v[i].size() <= n * m) {
      for (pii& p1: v[i - 1]) {
        for (pii& p2: v[i]) {
          Set(dp[p2.X][p2.Y], dp[p1.X][p1.Y] + dis(p1, p2));
        }
      }
    } else {
      memset(d, -1, sizeof d);
      for (pii& p: v[i - 1]) {
        d[p.X][p.Y] = dp[p.X][p.Y];
      }
      sort(v[i - 1].begin(), v[i - 1].end(), cmp);
      x = 1;
      q.push(v[i - 1][0]);
      while (!q.empty()) {
        pii k = q.front();
        q.pop();
        while (x < v[i - 1].size() && dp[v[i - 1][x].X][v[i - 1][x].Y] <= d[k.X][k.Y]) {
          q.push(v[i - 1][x++]);
        }
        for (int j = 0; j < 4; ++j) {
          int a = k.X + dx[j], b = k.Y + dy[j];
          if (a >= 1 && a <= n && b >= 1 && b <= m && d[a][b] == -1) {
            d[a][b] = d[k.X][k.Y] + 1;
            q.push(make_pair(a, b));
          }
        }
        if (q.empty() && x < v[i - 1].size()) {
          q.push(v[i - 1][x++]);
        }
      }
      for (pii& p: v[i]) {
        dp[p.X][p.Y] = d[p.X][p.Y];
      }
    }
  }
  printf("%d\n", dp[v[p][0].X][v[p][0].Y]);
  return 0;
}
相关文章