BZOJ 1499【动态规划/单调队列优化】

NOI2005 瑰丽华尔兹

[Description]

舞厅是一个N行M列的矩阵,矩阵中的某些方格上堆放了一些家具,其他的则是空地。钢琴可以在空地上滑动,但不能撞上家具或滑出舞厅,否则会损坏钢琴和家具,引来难缠的船长。每个时刻,钢琴都会随着船体倾斜的方向向相邻的方格滑动一格,相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法:如果不施魔法,则钢琴会滑动;如果施魔法,则钢琴会原地不动。艾米丽是个天使,她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行路程尽量长,这样1900会非常高兴,同时也有利于治疗托尼的晕船。但艾米丽还太小,不会算,所以希望你能帮助她。

[Input]

输入文件的第一行包含5个数N, M, x, y和K。N和M描述舞厅的大小,x和y为钢琴的初始位置(x行y列);我们对船体倾斜情况是按时间的区间来描述的,且从1开始计量时间,比如“在[1, 3]时间里向东倾斜,[4, 5]时间里向北倾斜”,因此这里的K表示区间的数目。以下N行,每行M个字符,描述舞厅里的家具。第i行第j列的字符若为‘ . ’,则表示该位置是空地;若为‘ x ’,则表示有家具。以下K行,顺序描述K个时间区间,格式为:si ti di。表示在时间区间[si, ti]内,船体都是向di方向倾斜的。di为1, 2, 3, 4中的一个,依次表示北、南、西、东(分别对应矩阵中的上、下、左、右)。输入保证区间是连续的,即 s1 = 1 si = ti-1 + 1 (1 < i ≤ K) tK = T

[Hint]

$n,m≤200,k≤200,ti-si≤200$(我猜测)

[Solution]

网上题解说DP+单调队列优化,正好我前几天看了一下,于是准备打这题。
朴素算法很容易推出,设f[sec][x][y]为第sec个时段结束后停留在(x,y)的最长距离,以di=1为例,我们直接推出状态转移方程:$$f[sec][x][y]=f[sec][i][j]=max(f[sec][i][j],f[sec-1][k][j]+k-i),k∈(i,min(n,i+ti-si)且(i-k.j)无家具$$
其他三个类似。
这样的算法复杂度为O(knm(ti-si))约等于$10^{9}$,时间是十分吃紧的,然而我打了个试试,竟然卡过了==‘’,正好2000ms,代码如下:

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
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;

inline int readint(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

const int inf=~0u>>1;
const int maxn=200+10;
char s[maxn][maxn];
int f[maxn][maxn][maxn];

int main(){
int n=readint(),m=readint(),x=readint(),y=readint(),t=readint();
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
memset(f,128,sizeof(f)); f[0][x][y]=0;
for(int sec=1;sec<=t;sec++){
int l=readint(),r=readint(),last=r-l+1,dir=readint();
if(dir==1){
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++) if(s[i][j]-'x')
for(int k=i,lim=min(n,i+last);k<=lim;k++)
if(s[k][j]-'x') f[sec][i][j]=max(f[sec][i][j],f[sec-1][k][j]+k-i);
else break;
}
else if(dir==2){
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++) if(s[i][j]-'x')
for(int k=i,lim=max(1,i-last);k>=lim;k--)
if(s[k][j]-'x') f[sec][i][j]=max(f[sec][i][j],f[sec-1][k][j]+i-k);
else break;
}
else if(dir==3){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(s[i][j]-'x')
for(int k=j,lim=min(m,j+last);k<=lim;k++)
if(s[i][k]-'x') f[sec][i][j]=max(f[sec][i][j],f[sec-1][i][k]+k-j);
else break;
}
else{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(s[i][j]-'x')
for(int k=j,lim=max(1,j-last);k>=lim;k--)
if(s[i][k]-'x') f[sec][i][j]=max(f[sec][i][j],f[sec-1][i][k]+j-k);
else break;
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,f[t][i][j]);
printf("%d",ans);
return 0;
}

最后一步显然可以用单调队列优化,可能是因为deque太慢的原因,用时1640ms,这里同样给出代码:

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<deque> 
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;

inline int readint(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

const int maxn=200+10;
char s[maxn][maxn];
int f[maxn][maxn][maxn];

deque<int> q,pos;
void insert(int x,int p){
while(!q.empty() && q.back()<=x) q.pop_back(),pos.pop_back();
q.push_back(x),pos.push_back(p);
}
void remove(int p,int last,bool o){
if(o) while(!q.empty() && p-pos.front()>last) q.pop_front(),pos.pop_front();
else while(!q.empty() && pos.front()-p>last) q.pop_front(),pos.pop_front();
}

int main(){
int n=readint(),m=readint(),x=readint(),y=readint(),t=readint();
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
memset(f,128,sizeof(f)); f[0][x][y]=0;
for(int sec=1;sec<=t;sec++){
int l=readint(),r=readint(),last=r-l+1,dir=readint();
if(dir==1){
for(int j=1;j<=m;j++){
q.clear(),pos.clear();
for(int i=n;i;i--)
if(s[i][j]-'x'){
insert(f[sec-1][i][j]+i,i);
remove(i,last,0);
f[sec][i][j]=q.front()-i;
}
else q.clear(),pos.clear();
}
}
else if(dir==2){
for(int j=1;j<=m;j++){
q.clear(),pos.clear();
for(int i=1;i<=n;i++)
if(s[i][j]-'x'){
insert(f[sec-1][i][j]-i,i);
remove(i,last,1);
f[sec][i][j]=q.front()+i;
}
else q.clear(),pos.clear();
}
}
else if(dir==3){
for(int i=1;i<=n;i++){
q.clear(),pos.clear();
for(int j=m;j;j--)
if(s[i][j]-'x'){
insert(f[sec-1][i][j]+j,j);
remove(j,last,0);
f[sec][i][j]=q.front()-j;
}
else q.clear(),pos.clear();
}
}
else{
for(int i=1;i<=n;i++){
q.clear(),pos.clear();
for(int j=1;j<=m;j++)
if(s[i][j]-'x'){
insert(f[sec-1][i][j]-j,j);
remove(j,last,1);
f[sec][i][j]=q.front()+j;
}
else q.clear(),pos.clear();
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,f[t][i][j]);
printf("%d",ans);
return 0;
}