P2254 NOI2005 瑰丽华尔兹 题解-代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=40009,M=202,inf=0x7f7f7f7f;
ll n,m,X,Y,k;
char c[M][M];
ll f[M][M];
bool ot(ll x,ll y)
{
	return x<1||x>n||y<1||y>m;
}
ll dx[5]={0,-1,1,0,0};
ll dy[5]={0,0,0,-1,1};
struct node
{
	ll num,start;
	//贡献数值 起点 
}q[N];
void sol(ll x,ll y,ll len,ll d)
{
	ll hh=1,tt=0;
	for(int stp=1;!ot(x,y);stp++,x+=dx[d],y+=dy[d])
	{
		if(c[x][y]=='x')
		{
			hh=1,tt=0;
			continue;
		}
		//队首最优 
		while(hh<=tt&&q[tt].num+stp-q[tt].start<f[x][y])tt--;
		q[++tt]=(node){f[x][y],stp};//加入所需元素 
		while(q[tt].start-q[hh].start>len)hh++;//弹出越界队首 
		f[x][y]=q[hh].num+stp-q[hh].start;
	}
}
int main()
{
	scanf("%lld%lld%lld%lld%lld",&n,&m,&X,&Y,&k);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	cin>>c[i][j];
	memset(f,-inf,sizeof(f));
	f[X][Y]=0;
	for(int i=1;i<=k;i++)
	{
		ll l,r,d,len;
		scanf("%lld%lld%lld",&l,&r,&d);
		len=r-l+1;
		if(d==1)
		{
			for(int i=1;i<=m;i++)
			sol(n,i,len,d);
		}
		if(d==2)
		{
			for(int i=1;i<=m;i++)
			sol(1,i,len,d);
		}
		if(d==3)
		{
			for(int i=1;i<=n;i++)
			sol(i,m,len,d);
		}
		if(d==4)
		{
			for(int i=1;i<=n;i++)
			sol(i,1,len,d);
		}
	}
	ll ans=-inf;
	for(int x=1;x<=n;x++)
	for(int y=1;y<=n;y++)
	ans=max(ans,f[x][y]);
	printf("%lld",ans);
	return 0;
}