bzoj 1499 [NOI2005]瑰丽华尔兹——单调队列优化dp

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1499

简单的单调队列优化dp。（然而当时却WA得不行。今天总算填了坑）

注意滚动数组赋初值应当继承上一次的该位置的值。还有转移的时候取个max。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=,INF=;//

int n,m,x,y,T,l,r,d,dp[][N][N],ans,q[N],h,t;

char ch[N][N];

int main()

{

    scanf("%d%d%d%d%d ",&n,&m,&x,&y,&T);

    for(int i=;i<=n;i++)cin>>(ch[i]+);

    memset(dp,-,sizeof dp);dp[][x][y]=;

    for(int s=;s<=T;s++)

    {

        scanf("%d%d%d",&l,&r,&d);int u=(s&),v=!u;int w=r-l+;

        if(d==)

        {

//            q[0]=n;

            for(int j=;j<=m;j++)

            {

                for(int i=n;i;i--)

                {

                    dp[u][i][j]=dp[v][i][j];//

                    if(ch[i][j]=='x')

                    {

//                        h=0;t=0;q[0]=i-1;continue;

                        h=;t=;continue;

                    }

                    while(h<=t&&q[h]-i>w)h++;

                    while(h<=t&&dp[v][i][j]>=dp[v][q[t]][j]+(q[t]-i))t--;q[++t]=i;

                    if(dp[v][q[h]][j]>-INF||(q[h]==x&&j==y))dp[u][i][j]=max(dp[u][i][j],dp[v][q[h]][j]+(q[h]-i));//

//                    printf("dp[%d][%d]=%d(dp[%d][%d]=%d i=%d q[%d]=%d)\n",i,j,dp[u][i][j],q[h],j,dp[v][q[h]][j],i,h,q[h]);

                }

                h=;t=;//

            }

        }

        else if(d==)

        {

//            q[0]=1;

            for(int j=;j<=m;j++)

            {

                for(int i=;i<=n;i++)

                {

                    dp[u][i][j]=dp[v][i][j];//

                    if(ch[i][j]=='x')

                    {

//                        h=0;t=0;q[0]=i+1;continue;

                        h=;t=;continue;

                    }

                    while(h<=t&&i-q[h]>w)h++;

                    while(h<=t&&dp[v][i][j]>=dp[v][q[t]][j]+(i-q[t]))t--;q[++t]=i;

                    if(dp[v][q[h]][j]>-INF||(q[h]==x&&j==y))dp[u][i][j]=max(dp[u][i][j],dp[v][q[h]][j]+(i-q[h]));//

//                    printf("dp[%d][%d]=%d(dp[%d][%d]=%d i=%d q[%d]=%d)\n",i,j,dp[u][i][j],q[h],j,dp[v][q[h]][j],i,h,q[h]);

                }

                h=;t=;//

            }

        }

        else if(d==)

        {

//            q[0]=m;

            for(int i=;i<=n;i++)

            {

                for(int j=m;j;j--)

                {

                    dp[u][i][j]=dp[v][i][j];//

                    if(ch[i][j]=='x')

                    {

//                        h=0;t=0;q[0]=j-1;continue;

                        h=;t=;continue;

                    }

                    while(h<=t&&q[h]-j>w)h++;

                    while(h<=t&&dp[v][i][j]>=dp[v][i][q[t]]+(q[t]-j))t--;q[++t]=j;

                    if(dp[v][i][q[h]]>-INF||(i==x&&q[h]==y))dp[u][i][j]=max(dp[u][i][j],dp[v][i][q[h]]+(q[h]-j));//

//                    printf("dp[%d][%d]=%d(dp[%d][%d]=%d j=%d q[%d]=%d)\n",i,j,dp[u][i][j],i,q[h],dp[v][i][q[h]],j,h,q[h]);

                }

                h=;t=;//

            }

        }

        else{

//            q[0]=1;

            for(int i=;i<=n;i++)

            {

                for(int j=;j<=m;j++)

                {

                    dp[u][i][j]=dp[v][i][j];//

                    if(ch[i][j]=='x')

                    {

//                        h=0;t=0;q[0]=j+1;continue;

                        h=;t=;continue;

                    }

                    while(h<=t&&j-q[h]>w)h++;

                    while(h<=t&&dp[v][i][j]>=dp[v][i][q[t]]+(j-q[t]))t--;q[++t]=j;

                    if(dp[v][i][q[h]]>-INF||(i==x&&q[h]==y))dp[u][i][j]=max(dp[u][i][j],dp[v][i][q[h]]+(j-q[h]));//

//                    printf("dp[%d][%d]=%d(dp[%d][%d]=%d j=%d q[%d]=%d)\n",i,j,dp[u][i][j],q[h],j,dp[v][q[h]][j],j,h,q[h]);

                }

                h=;t=;//

            }

        }

    }

    int u=(T&);

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) ans=max(ans,dp[u][i][j]);

    printf("%d",ans);

    return ;

}