[NOI2005]瑰丽华尔兹

朴素的动规很好考虑，f[i, x, y]表示第i个时间段结束的时候在(x, y)位置的最大滑动距离。那么就有朴素方程： 
f[i, x, y] = max{ f[i-1, x+s, y] + s }  (d[i] = 1)
             max{ f[i-1, x-s, y] + s }  (d[i] = 2) 
             max{ f[i-1, x, y+s] + s }  (d[i] = 3)
             max{ f[i-1, x, y-s] + s }  (d[i] = 4)

其中s为0到最远滑行距离，也就是min{第i时间段的时间, 障碍物到当前点的距离}

时间复杂度O(knm*最大时间)，其中最大时间<=max(n, m)

优化：

考虑d[i] = 1的情况：

f[i, x, y] = max{ f[i-1, x+s, y] + s }  (d[i] = 1)
           = max{ f[i-1, x+s, y] + (x+s) } - x
令g(k) = f[i-1, x+s, y] + (x+s)，那么：
f[i, x, y] = max{ g(k) } - x

于是我们可以对于同一个i和y的每一个x，维护一个单调递减的队列，每次取出队头-x就是f[i, x, y]的值。

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

#include <cstdio>
#include <cstring>

#define MAX(x, y) if (x < y) x = y;
struct Item
{
  int time, value;
  Item(const int t = 0, const int v = 0): time(t), value(v) { }
};
char map[201][201];
int n, m, x0, y0, p, last[201], d[201], f[201][201][201];
inline void update(const int i, int x, int y, const int dx, const int dy)
{
  static Item Q[201];
  static int head, tail;
  head = 0, tail = -1;
  for (int now = 1; x >= 1 && x <= n && y >= 1 && y <= m; x += dx, y += dy, ++now)
  {
    if (map[x][y] != '.')
    {
      head = 0, tail = -1;
      f[i][x][y] = 0xC0C0C0C0;
      continue;
    }
    while (head <= tail && f[i-1][x][y]-now >= Q[tail].value) --tail;
    Q[++tail] = Item(now, f[i-1][x][y]-now);
    while (head+1 <= tail && now-Q[head].time > last[i]) ++head;
    f[i][x][y] = Q[head].value+now;
  }
}
int main()
{
  memset(f[0], 0xC0, sizeof(f[0]));
  scanf("%d%d%d%d%dn", &n, &m, &x0, &y0, &p);
  for (int i = 1; i <= n; ++i)
    scanf("%sn", &map[i][1]);
  for (int i = 1, st, ed; i <= p; ++i)
  {
    scanf("%d%d%d", &st, &ed, d+i);
    last[i] = ed-st+1;
  }

  f[0][x0][y0] = 0;
  for (int i = 1; i <= p; ++i)
    switch (d[i])
    {
      case 1: for (int y = 1; y <= m; ++y) update(i, n, y, -1,  0); break;
      case 2: for (int y = 1; y <= m; ++y) update(i, 1, y, +1,  0); break;
      case 3: for (int x = 1; x <= n; ++x) update(i, x, m,  0, -1); break;
      case 4: for (int x = 1; x <= n; ++x) update(i, x, 1,  0, +1);
    }
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      MAX(ans, f[p][i][j]);
  printf("%d", ans);
}

Comments