题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1499
朴素DP方程很好想,以右移为例,就是 f[i][x][y]=max(f[i][x][y],f[i-1][x][j]+y-j) ;
每一行/列会用到一些相同的状态更新,所以可以用单调队列优化。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=,inf=0x3f3f3f3f;
int n,m,K,st,ed,f[][maxn][maxn],xx[]={,-,,,},yy[]={,,,-,},L,ans;
char s[maxn][maxn];
struct N{
int pos,ans;
}q[maxn];
void dp(int x,int y,int d,int nw)
{
int h=,t=;N tmp;
for(int i=;x&&y&&x<=n&&y<=m;i++,x+=xx[d],y+=yy[d])//i为与原来的y的差距,注意不要与y搞混
{
if(s[x][y]=='x')h=,t=;//h!=0
tmp.pos=i;tmp.ans=f[nw^][x][y];
while(h<=t&&i-q[h].pos>L)h++;//i //<=
while(h<=t&&tmp.ans>=q[t].ans+i-q[t].pos)t--;//i
q[++t]=tmp;
if(h>t)f[nw][x][y]=-inf;//
else f[nw][x][y]=q[h].ans+i-q[h].pos;
ans=max(ans,f[nw][x][y]);
}
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&st,&ed,&K);
for(int i=;i<=n;i++)cin>>s[i]+;
memset(f,-0x3f,sizeof f);
f[][st][ed]=;
int l,r,d,nw=;
while(K--)
{
nw^=;
scanf("%d%d%d",&l,&r,&d);
L=r-l+;
if(d==)for(int i=;i<=m;i++)dp(n,i,d,nw);
if(d==)for(int i=;i<=m;i++)dp(,i,d,nw);
if(d==)for(int j=;j<=n;j++)dp(j,m,d,nw);
if(d==)for(int j=;j<=n;j++)dp(j,,d,nw);
}
printf("%d",ans);
return ;
}