「BZOJ1499」[NOI2005]瑰丽华尔兹

Description

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

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

Input

输入文件的第一行包含55个数N,M,x,yN, M, x, yKKNNMM描述舞厅的大小,xxyy为钢琴的初始位置;我们对船体倾斜情况是按时间的区间来描述的,且从11开始计算时间,比如“在[1,3][1,3]时间里向东倾斜,[4,5][4,5]时间里向北倾斜”,因此这里的KK表示区间的数目。
以下NN行,每行MM个字符,描述舞厅里的家具。第ii行第jj 列的字符若为.,则表示该位置是空地;若为x,则表示有家具。
以下KK行,顺序描述KK个时间区间,格式为:sitidi(1iK)s_i t_i d_i(1 \leq i \leq K)。表示在时间区间[si,ti][s_i,t_i]内,船体都是向did_i方向倾斜的。did_i1,2,3,41, 2, 3, 4中的一个,依次表示北、南、西、东(分别对应矩阵中的上、下、左、右)。输入保证区间是连续的,即

s1=1s_1 = 1

ti=si1+1(1<iK)t_i = s_{i-1} + 1 (1 < i \leq K)

tK=Tt_K = T

Output

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

Sample Input

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

Sample Output

1
6

HINT


钢琴在×位置上时天使使用一次魔法,因此滑动总长度为66
50%50\%的数据中,1N,M200,T2001\leq N, M\leq 200,T\leq 200
100%100\%的数据中,1N,M200,K200,T400001\leq N, M\leq 200,K\leq200,T\leq 40000

Solution

force

ft,i,jf_{t,i,j}表示时间为tt(sx,sy)(sx,sy)(i,j)(i,j)能走的最长距离
ft,i,j=max{ft1,i,j+1}f_{t,i,j}=\max\{f_{t-1,i',j'}+1\}
时间复杂度O(TNM)O(TNM)

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210, M = 210;

int n, m, sx, sy, K;
char s[N][M];
int f[2][N][M];
bool t;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void update(int d) {
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) f[t][i][j] = f[t ^ 1][i][j];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) if(s[i][j] != 'x'){
int r = dx[d] + i;
int c = dy[d] + j;
if(r < 1 || r > n || c < 1 || c > m || s[r][c] == 'x') continue;
f[t][r][c] = max(f[t][r][c], f[t ^ 1][i][j] + 1);
}
}
int main() {
n = read(), m = read(), sx = read(), sy = read(), K = read();
for(int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
memset(f[0],-0x3f,sizeof f[0]);
f[0][sx][sy] = 0;
for(int i = 1; i <= K; ++i) {
int l = read(), r = read(), d = read() - 1;
for(int j = l; j <= r; ++j) {
t ^= 1;
update(d);
}
}
int ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
ans = max(ans, f[t][i][j]);
}
writeln(ans);
return 0;
}

std

显然一段一段可以一起算。然后转移用单调队列优化,每个方向都单独讨论。
时间复杂度变成O(nmK)O(nmK)

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210, M = 210;

int n, m, sx, sy, K;
char s[N][M];
int f[2][N][M];
bool t;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int q[N], head, tail;
void solve1(int len) {
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) f[t][i][j] = f[t ^ 1][i][j];
for(int j = 1; j <= m; ++j) {head = 1, tail = 0;
for(int i = n; i ; --i) {
if(s[i][j] == 'x') {
head = 1; tail = 0;
continue;
}
while(head <= tail && q[head] - i > len) ++head;
if(head <= tail) f[t][i][j] = max(f[t][i][j], f[t ^ 1][q[head]][j] + q[head] - i);
while(head <= tail && f[t ^ 1][i][j] >= f[t ^ 1][q[tail]][j] + q[tail] - i) --tail;
q[++tail] = i;
}
}
}
void solve2(int len) {
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) f[t][i][j] = f[t ^ 1][i][j];
for(int j = 1; j <= m; ++j) {head = 1, tail = 0;
for(int i = 1; i <= n; ++i) {
if(s[i][j] == 'x') {
head = 1; tail = 0;
continue;
}
while(head <= tail && i - q[head] > len) ++head;
if(head <= tail) f[t][i][j] = max(f[t][i][j], f[t ^ 1][q[head]][j] + i - q[head]);
while(head <= tail && f[t ^ 1][i][j] >= f[t ^ 1][q[tail]][j] + i - q[tail]) --tail;
q[++tail] = i;
}
}
}

void solve3(int len) {
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) f[t][i][j] = f[t ^ 1][i][j];
for(int i = 1;i <= n; ++i) {head = 1, tail = 0;
for(int j = m; j; --j){
if(s[i][j] == 'x') {
head = 1; tail = 0;
continue;
}
while(head <= tail && q[head] - j > len) ++head;
if(head <= tail) f[t][i][j] = max(f[t][i][j], f[t ^ 1][i][q[head]] + q[head] - j);
while(head <= tail && f[t ^ 1][i][j] >= f[t ^ 1][i][q[tail]] + q[tail] - j) --tail;
q[++tail] = j;
}
}
}
void solve4(int len) {
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) f[t][i][j] = f[t ^ 1][i][j];
for(int i = 1;i <= n; ++i) {head = 1, tail = 0;
for(int j = 1; j <= m; ++j){
if(s[i][j] == 'x') {
head = 1; tail = 0;
continue;
}
while(head <= tail && j - q[head] > len) ++head;
if(head <= tail) f[t][i][j] = max(f[t][i][j], j - q[head] + f[t ^ 1][i][q[head]]);
while(head <= tail && f[t ^ 1][i][j] >= f[t ^ 1][i][q[tail]] + j - q[tail]) --tail;
q[++tail] = j;
}
}
}
int main() {
n = read(), m = read(), sx = read(), sy = read(), K = read();
for(int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
memset(f[0],-0x3f,sizeof f[0]);
f[0][sx][sy] = 0;
for(int i = 1; i <= K; ++i) {
int l = read(), r = read(), d = read() - 1;
t ^= 1;
if(d == 0) solve1(r - l + 1);
if(d == 1) solve2(r - l + 1);
if(d == 2) solve3(r - l + 1);
if(d == 3) solve4(r - l + 1);
}
int ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
ans = max(ans, f[t][i][j]);
}
writeln(ans);
return 0;
}