bzoj1499 [NOI2005]瑰丽华尔兹——单调队列优化DP

题目：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 ;

}