[NOI2005] 瑰丽华尔兹

GitHub 跳转原题关系图返回列表

把每段固定方向的时间看成一次行或列上的区间转移，设 dp[x][y] 表示当前位置最大滑行距离，再用单调队列优化每段的滑动窗口最大值。

OJ: luogu

题目 ID: P2254

难度:提高+/省选-

标签:动态规划单调队列网格

日期: 2026-06-21 06:17

题意

舞厅是一个 n x m 的网格，x 表示有家具，. 表示空地。

钢琴一开始在 (start_x, start_y)。

接下来有 k 段时间，第 i 段时间内船体倾斜方向固定。

这一段里的每一秒：

可以施魔法，让钢琴原地不动
也可以不施魔法，让钢琴朝当前固定方向滑动一格

但钢琴不能撞到家具，也不能滑出舞厅。

要求最大化总滑行距离。

思路

先看一个小数据暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int MAXT = 205;
const int NEG_INF = -1000000000;

int n, m, start_x, start_y, seg_cnt;
char grid_map[MAXN][MAXN];
int dp[MAXN][MAXN], nxt_dp[MAXN][MAXN];
int dir_list[MAXT], total_time;
int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：按时间一秒一秒地做 DP。
    // 每一秒只有两种选择：施魔法原地不动，或者顺着当前方向滑动一格。
    cin >> n >> m >> start_x >> start_y >> seg_cnt;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid_map[i][j];
        }
    }

    total_time = 0;
    for (int i = 1; i <= seg_cnt; i++) {
        int l, r, d;
        cin >> l >> r >> d;
        int len = r - l + 1;
        for (int t = 1; t <= len; t++) {
            dir_list[++total_time] = d;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = NEG_INF;
        }
    }
    dp[start_x][start_y] = 0;

    for (int t = 1; t <= total_time; t++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                nxt_dp[i][j] = NEG_INF;
            }
        }

        int d = dir_list[t];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dp[i][j] <= NEG_INF / 2) {
                    continue;
                }

                // 这一秒施魔法，原地不动。
                nxt_dp[i][j] = max(nxt_dp[i][j], dp[i][j]);

                // 这一秒不施魔法，顺着当前方向滑一格。
                int ni = i + dx[d];
                int nj = j + dy[d];
                if (ni >= 1 && ni <= n && nj >= 1 && nj <= m &&
                    grid_map[ni][nj] != 'x') {
                    nxt_dp[ni][nj] = max(nxt_dp[ni][nj], dp[i][j] + 1);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = nxt_dp[i][j];
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << '\n';
    return 0;
}

暴力按“秒”来做 DP。

设 dp[x][y] 表示当前这一秒结束后，钢琴停在 (x,y) 的最大滑行距离。

每秒只有两种决策：

施魔法，留在原地
不施魔法，沿当前方向走一格

这样总时间是 T，总复杂度大约是 $O(T * n * m)$ 。

本题 T 最多到 40000，虽然不算特别离谱，但如果把每段时间单独拆成一秒一秒处理，常数会比较大，而且很难进一步利用“同一段方向固定”这个性质。

正解的关键是按“整段时间”处理。

设：

dp[x][y] 表示处理完前若干段时间后，钢琴停在 (x,y) 的最大滑行距离。

考虑某一整段时间，方向固定，长度为 len。

假设这一段方向是“向右”。

如果这一段结束后停在 (x,y)，那么这一整段开始时一定在同一行的某个位置 (x,k)，并且：

k <= y
y-k <= len
从 k 到 y 中间不能跨过家具

如果这段时间里从 k 走到了 y，新增的滑行距离就是 y-k，所以转移式是：

dp[x][y] = max(old_dp[x][k] + y-k)

整理一下：

dp[x][y] = y + max(old_dp[x][k] - k)

这里 k 的可选范围是一个长度不超过 len+1 的滑动窗口。

对固定的一行来说，y 从左到右枚举时，这个窗口也在一起右移，所以可以用单调队列维护

old_dp[x][k] - k

的最大值。

向左、向上、向下完全同理，只是把维护的式子换成：

向左：old_dp[x][k] + k
向上：old_dp[k][y] + k
向下：old_dp[k][y] - k

另外，家具会把一行或一列切成若干互不连通的连续空地段。

一旦扫到家具，这一格就不能落脚，也不能跨过去，因此单调队列必须立刻清空，表示窗口不能跨障碍延续。

于是每一段时间都可以在 $O(n*m)$ 内完成转移，总复杂度就是 $O(k*n*m)$ 。

DP 转移方程

核心状态：

dp[x][y] 为处理完若干段后停在格子的最大距离

核心转移：

向右: new[x][y]=y+max(old[x][k]-k)

答案收束：

所有格子的最大 dp

代码

cpp

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const int NEG_INF = -1000000000;

int n, m, start_x, start_y, seg_cnt;
char grid_map[MAXN][MAXN];
// dp[x][y]：处理完当前这段时间后，钢琴停在 (x,y) 的最大滑行距离。
int dp[MAXN][MAXN];
// old_dp 是上一段时间结束后的状态，当前段的所有转移都只能从它转来。
int old_dp[MAXN][MAXN];
// 单调队列里存的是某一行/列上的候选下标。
int q[MAXN];

struct Segment {
    int l, r, dir;
} seg[MAXN];

// 处理“向上滑动 len 步”的整段转移。
void move_up(int len) {
    for (int col = 1; col <= m; col++) {
        int head = 0, tail = -1;
        for (int row = n; row >= 1; row--) {
            if (grid_map[row][col] == 'x') {
                head = 0;
                tail = -1;
                dp[row][col] = NEG_INF;
                continue;
            }

            // 向上最多走 len 步，所以候选起点行号不能超过 row + len。
            while (head <= tail && q[head] > row + len) {
                head++;
            }

            // 转移式：
            // old_dp[k][col] + (k - row)
            // 对固定 row 来说，只要维护 old_dp[k][col] + k 的最大值即可。
            while (head <= tail &&
                   old_dp[q[tail]][col] + q[tail] <= old_dp[row][col] + row) {
                tail--;
            }
            q[++tail] = row;

            if (old_dp[q[head]][col] <= NEG_INF / 2) {
                dp[row][col] = NEG_INF;
            } else {
                dp[row][col] = old_dp[q[head]][col] + q[head] - row;
            }
        }
    }
}

// 处理“向下滑动 len 步”的整段转移。
void move_down(int len) {
    for (int col = 1; col <= m; col++) {
        int head = 0, tail = -1;
        for (int row = 1; row <= n; row++) {
            if (grid_map[row][col] == 'x') {
                head = 0;
                tail = -1;
                dp[row][col] = NEG_INF;
                continue;
            }

            // 向下最多走 len 步，所以候选起点行号不能小于 row - len。
            while (head <= tail && q[head] < row - len) {
                head++;
            }

            // 转移式：
            // old_dp[k][col] + (row - k)
            // 对固定 row 来说，维护 old_dp[k][col] - k 的最大值。
            while (head <= tail &&
                   old_dp[q[tail]][col] - q[tail] <= old_dp[row][col] - row) {
                tail--;
            }
            q[++tail] = row;

            if (old_dp[q[head]][col] <= NEG_INF / 2) {
                dp[row][col] = NEG_INF;
            } else {
                dp[row][col] = old_dp[q[head]][col] - q[head] + row;
            }
        }
    }
}

// 处理“向左滑动 len 步”的整段转移。
void move_left(int len) {
    for (int row = 1; row <= n; row++) {
        int head = 0, tail = -1;
        for (int col = m; col >= 1; col--) {
            if (grid_map[row][col] == 'x') {
                head = 0;
                tail = -1;
                dp[row][col] = NEG_INF;
                continue;
            }

            // 向左最多走 len 步，所以候选起点列号不能超过 col + len。
            while (head <= tail && q[head] > col + len) {
                head++;
            }

            // 转移式：
            // old_dp[row][k] + (k - col)
            while (head <= tail &&
                   old_dp[row][q[tail]] + q[tail] <= old_dp[row][col] + col) {
                tail--;
            }
            q[++tail] = col;

            if (old_dp[row][q[head]] <= NEG_INF / 2) {
                dp[row][col] = NEG_INF;
            } else {
                dp[row][col] = old_dp[row][q[head]] + q[head] - col;
            }
        }
    }
}

// 处理“向右滑动 len 步”的整段转移。
void move_right(int len) {
    for (int row = 1; row <= n; row++) {
        int head = 0, tail = -1;
        for (int col = 1; col <= m; col++) {
            if (grid_map[row][col] == 'x') {
                head = 0;
                tail = -1;
                dp[row][col] = NEG_INF;
                continue;
            }

            // 向右最多走 len 步，所以候选起点列号不能小于 col - len。
            while (head <= tail && q[head] < col - len) {
                head++;
            }

            // 转移式：
            // old_dp[row][k] + (col - k)
            while (head <= tail &&
                   old_dp[row][q[tail]] - q[tail] <= old_dp[row][col] - col) {
                tail--;
            }
            q[++tail] = col;

            if (old_dp[row][q[head]] <= NEG_INF / 2) {
                dp[row][col] = NEG_INF;
            } else {
                dp[row][col] = old_dp[row][q[head]] - q[head] + col;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> start_x >> start_y >> seg_cnt;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid_map[i][j];
        }
    }
    for (int i = 1; i <= seg_cnt; i++) {
        cin >> seg[i].l >> seg[i].r >> seg[i].dir;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = NEG_INF;
        }
    }
    dp[start_x][start_y] = 0;

    for (int i = 1; i <= seg_cnt; i++) {
        // 这一段时间的总秒数。
        int len = seg[i].r - seg[i].l + 1;

        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                old_dp[x][y] = dp[x][y];
            }
        }

        // 方向编号：
        // 1 上，2 下，3 左，4 右
        if (seg[i].dir == 1) {
            move_up(len);
        } else if (seg[i].dir == 2) {
            move_down(len);
        } else if (seg[i].dir == 3) {
            move_left(len);
        } else {
            move_right(len);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度 $O(k * n * m)$ ，空间复杂度 $O(n * m)$ 。

总结

这题表面是在网格上模拟滑动，核心其实是“固定方向的一整段时间”的区间最值转移。

一旦把每一段压成一次行/列 DP，就能自然地看到单调队列优化的窗口结构。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P2254 [NOI2005] 瑰丽华尔兹

题目背景

你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？

众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼・布德曼・T.D.・柠檬・1900，朋友们都叫他 1900。

1900 在 20 世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上。很不幸，他刚出生就被抛弃，成了孤儿。1900 孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的世界。也许是对他命运的补偿，上帝派可爱的小天使艾米丽照顾他。可能是天使的点化，1900 拥有不可思议的钢琴天赋：从未有人教，从没看过乐谱，但他却能凭着自己的感觉弹出最沁人心脾的旋律。当 1900 的音乐获得邮轮上所有人的欢迎时，他才 8 岁，而此时，他已经乘着海轮往返欧美大陆 50 余次了。

虽说是钢琴奇才，但 1900 还是个孩子，他有着和一般男孩一样的好奇和调皮，只不过更多一层浪漫的色彩罢了：这是一个风雨交加的夜晚，海风卷起层层巨浪拍打着弗吉尼亚号，邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手迈克斯・托尼晕船了，1900 招呼托尼和他一起坐到舞厅里的钢琴上，然后松开了固定钢琴的闸，于是，钢琴随着海轮的倾斜滑动起来。准确的说，我们的主角 1900…

题目描述

不妨认为舞厅是一个 $N$ 行 $M$ 列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。

艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长，这样 1900 会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。

输入格式

输入文件的第一行包含 $5$ 个数 $N$ , $M$ , $x$ , $y$ 和 $K$ 。 $N$ 和 $M$ 描述舞厅的大小， $x$ 和 $y$ 为钢琴的初始位置；我们对船体倾斜情况是按时间的区间来描述的，且从 $1$ 开始计算时间，比如 “在 $[1, 3]$ 时间里向东倾斜， $[4, 5]$ 时间里向北倾斜”，因此这里的 $K$ 表示区间的数目。

以下 $N$ 行，每行 $M$ 个字符，描述舞厅里的家具。第 $i$ 行第 $j$ 列的字符若为 .，则表示该位置是空地；若为 x，则表示有家具。

以下 $K$ 行，顺序描述 $K$ 个时间区间，格式为： $s_i\ t_i\ d_i (1 \leq i \leq K)$ 。表示在时间区间 $[s_i, t_i]$ 内，船体都是向 $d_i$ 方向倾斜的。 $d_i$ 为 $1$ , $2$ , $3$ , $4$ 中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。输入保证区间是连续的，即

$s_1 = 1$ ， $s_i = t_{i-1} + 1 (1 < i \leq K)$ ， $t_K = T$ 。

输出格式

输出文件仅有 $1$ 行，包含一个整数，表示钢琴滑行的最长距离 (即格子数)。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
84 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3

输出 #1

text

说明/提示

钢琴的滑行路线：

钢琴在“×”位置上时天使使用一次魔法，因此滑动总长度为 $6$ 。

【数据范围】

$50\%$ 的数据中， $1\leq N, M\leq 200，T\leq 200$ ；

$100\%$ 的数据中， $1\leq N$ , $M \leq 200$ ， $K \leq 200$ ， $T\leq 40000$ 。

[NOI2005] 瑰丽华尔兹

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析