BZOJ1499： 瑰丽华尔兹（单调队列）

pro： 给出一个n*m的地图，刚开始人在(x,y)，每次给出一段区间(l,r,t)，表示在时间[l,r]内，可以使人向4个方向(t)移动一格，或者不动。求最大可以移动多少格。

sol： 考虑每一列（上下移）或者一行（左右移）的情况。以右移为例，我们可以很快列出dp方程：f[x][y][i]=max(f[x][y][i],f[x][j][i]+y-j)。这个dp方程我们可以用单调队列维护，所以复杂度就是nmk的。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int inf=1e9+;

int dp[maxn][maxn][],ans;

char c[maxn][maxn];

int X[]={,-,,,},Y[]={,,,-,};

int q[maxn][],head,tail,N,M,now;

int update(int x,int y,int tp,int tk)

{

    int res=dp[q[tp][]][q[tp][]][(tk^)&]+now-q[tp][];

    dp[x][y][tk&]=max(dp[x][y][tk&],res);

    return res;

}

int get(int tp,int tk)

{

    int res=dp[q[tp][]][q[tp][]][(tk^)&]+now-q[tp][];

    return res;

}

void work(int x,int y,int tK,int len,int opt)

{

    head=,tail=; now=;

    while(x>=&&x<=N&&y>=&&y<=M) {

        dp[x][y][tK&]=dp[x][y][(tK^)&];

        if(c[x][y]=='x') head=,tail=;

        while(tail>=head&&now-q[head][]>len) head++;

        while(tail>=head&&get(tail,tK)<dp[x][y][(tK^)&]) tail--;

        if(tail>=head)

            update(x,y,head,tK);

        ans=max(ans,dp[x][y][tK&]);

        tail++; q[tail][]=x; q[tail][]=y; q[tail][]=now++;

        x+=X[opt]; y+=Y[opt];

    }

}

int main()

{

    int K,x,y,L,R,opt;

    scanf("%d%d%d%d%d",&N,&M,&x,&y,&K);

    rep(i,,N) scanf("%s",c[i]+);

    rep(i,,N) rep(j,,M) rep(k,,K) dp[i][j][k]=-inf;

    dp[x][y][]=;

    rep(i,,K){

        scanf("%d%d%d",&L,&R,&opt);

        if(opt==) rep(j,,M) work(N,j,i,R-L+,opt);

        if(opt==) rep(j,,M) work(,j,i,R-L+,opt);

        if(opt==) rep(j,,N) work(j,M,i,R-L+,opt);

        if(opt==) rep(j,,N) work(j,,i,R-L+,opt);

    }

    printf("%d\n",ans);

    return ;

}