【bzoj1499】 NOI2005—瑰丽华尔兹

时间:2022-12-29 22:22:02

http://www.lydsy.com/JudgeOnline/problem.php?id=1499 (题目链接)

题意

  给出一个n*m的地图,刚开始人在(x,y),每次给出一段区间(l,r,t),表示在时间[l,r]内,可以使人向4个方向(t)移动一格。求最大可以移动多少格。

Solution

  考虑每一列(上下移)或者一行(左右移)的情况。以右移为例,我们可以很快列出dp方程:f[i][x][y]=max(f[i][x][y],f[i-1][x][j]+y-j)。这个dp方程我们可以用单调队列维护,所以复杂度就是nmk的。

代码

// bzoj1499
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=300;
int xx[]={0,-1,1,0,0},yy[]={0,0,0,-1,1};
int q[maxn],p[maxn],f[2][maxn][maxn];
int n,m,L,ans,X,Y,K;
char a[maxn][maxn]; void dp(int d,int x,int y,int t) {
int l=1,r=0,cnt=1;
while (x>=1 && y>=1 && x<=n && y<=m) {
if (a[x][y]=='x') l=1,r=0;
while (l<=r && cnt-p[l]>L) l++;
while (l<=r && q[r]+cnt<f[d^1][x][y]) r--;
q[++r]=f[d^1][x][y]-cnt;p[r]=cnt;
if (l>r) f[d][x][y]=-inf;
else f[d][x][y]=q[l]+cnt;
ans=max(ans,f[d][x][y]);
cnt++;
x+=xx[t];y+=yy[t];
}
}
int main() {
scanf("%d%d%d%d%d",&n,&m,&X,&Y,&K);
for (int i=1;i<=n;i++) scanf("%s",a[i]+1);
for (int i=0;i<=1;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=m;k++) f[i][j][k]=-inf;
int d=0;f[0][X][Y]=0;
for (int u,v,t,i=1;i<=K;i++) {
d^=1;
scanf("%d%d%d",&u,&v,&t);
L=v-u+1;
if (t==1) for (int j=1;j<=m;j++) dp(d,n,j,t);
if (t==2) for (int j=1;j<=m;j++) dp(d,1,j,t);
if (t==3) for (int j=1;j<=n;j++) dp(d,j,m,t);
if (t==4) for (int j=1;j<=n;j++) dp(d,j,1,t);
}
printf("%d",ans);
return 0;
}