题目描述

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

艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长。

给定 $k$ 个时间段 $l,r,d$，表示在 $[l,r]$ 时间段，钢琴沿 $d$ 方向移动（$d=1,2,3,4$依次表示北、南、西、东，即矩阵中的上、下、左、右）。可以在 $\forall t\in [l,r]$ 时刻施加魔法。

输入数据保证，$l_1=1$，$l_i=r_{i-1}+1,i\in [1,k)$。

$1\le n,m\le 200,k\le 200,r_k\le 40000$。

思路

首先考虑朴素的 dp。

对于第 $i$ 个时间段，最大移动距离为 $len=r-l+1$。

令 $f_{i,x,y}$ 表示在第 $i$ 个时间段后，钢琴位置在 $(x,y)$ 的最大移动距离，考虑分别从 $4$ 个方向转移过来。举 $1$ 为例子，那么显然有：
fi,x,y=max⁡x′=xx+leni{fi−1,x′,y+∣x−x′∣},d=1f_{i,x,y}=\max_{x'=x}^{x+len_i}\{f_{i-1,x',y}+|x-x'|\},d=1fi,x,y​=x′=xmaxx+leni​​{fi−1,x′,y​+∣x−x′∣},d=1

此时要按 $x^{\prime }:x\to x+le{n}_i$ 的顺序遍历，如果遇到障碍物或边界就可以直接 break，因为之后的会被挡住，就不能这个方向转移过来。

给一下暴力解法的 dp 部分代码，$\Theta (k{n}^3)$ 级别。

memset(f,-inf,sizeof(f));
f[0][X][Y]=0;
for(int i=1;i<=k;i++)
{
	for(int x=1;x<=n;x++)
	{
		for(int y=1;y<=m;y++)
		{
			if(a[i].d==1)
			{
				for(int xx=x;xx<=x+a[i].len;xx++)
				{
					if(ot(xx,y)||c[xx][y]=='x')break;
					f[i][x][y]=max(f[i][x][y],f[i-1][xx][y]+abs(x-xx));
				}
			}
			if(a[i].d==2)
			{
				for(int xx=x;xx>=x-a[i].len;xx--)
				{
					if(ot(xx,y)||c[xx][y]=='x')break;
					f[i][x][y]=max(f[i][x][y],f[i-1][xx][y]+abs(x-xx));
				}
			}
			if(a[i].d==3)
			{
				for(int yy=y;yy<=y+a[i].len;yy++)
				{
					if(ot(x,yy)||c[x][yy]=='x')break;
					f[i][x][y]=max(f[i][x][y],f[i-1][x][yy]+abs(y-yy));
				}
			}
			if(a[i].d==4)
			{
				for(int yy=y;yy>=y-a[i].len;yy--)
				{
					if(ot(x,yy)||c[x][yy]=='x')break;
					f[i][x][y]=max(f[i][x][y],f[i-1][x][yy]+abs(y-yy));
				}
			}
		}
	}
}

你会惊奇的发现过了，没准是大样例的 $x$ 比较多，不过不能满足于此。

考虑正解，将 $n$ 的幂次降一级，如果能做到 $\Theta (k{n}^2)$ 级别就很爽。

考虑使用单调队列，优化掉找最大值的那个 $\Theta (n)$ 或者 $\Theta (m)$。

（作者也好久没写过单调队列优化 dp 的题目了）

回忆一下单调队列优化 dp 的步骤：加入所需元素、弹出越界队首、获取答案。

单调队列 $q$ 维护 dp 的最大值和步数起始点，维护队头最优，这样还可以把时间段维度 $i$ 滚动掉。

假设枚举到点 $(x,y)$，首先弹出小于 $f_{x,y}$ 的队尾，拿 $f_{x,y}$ 压入队尾；然后将距离队尾起始点大于 $le{n}_i$ 的队头弹出，最后剩下的队头就是最优解，也就是前继状态的 dp 最大值加上“（本行或本列上）跳的步数-（本行或本列上）起始点”：
$$f_{x,y}=q[head].num+(stp-q[head].start)$$

以方向为 $1$（上）举例，那么对于 $1\sim m$ 每一列 $i$，从底部的 $(n,i)$ 开始枚举，向上跳，用上面的思路写就好了。

代码

#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;
}