bzoj1499: [NOI2005]瑰丽华尔兹&&codevs1748 单调队列优化dp

这道题 网上题解还是很多很好的 强烈推荐黄学长 码风真的好看 神犇传送门 学习学习 算是道单调队列优化dp的裸题吧

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,sx,sy,k,ans;

int head,tail,now;

char a[M][M];

int f[M][M][M],q[M],pos[M];

int xi[]={,-,,,},yi[]={,,,-,};

bool pd(int x,int y){return (x>=&&x<=n&&y>=&&y<=m);}

void push_ans(int now,int w){

    if(w==-inf) return ;

    while(head<=tail&&q[tail]<w-now) tail--;

    q[++tail]=w-now;

    pos[tail]=now;

}

void dp(int i,int x,int y,int d,int l){

    head=; tail=;

    int now=;

    while(pd(x,y)){

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

        else push_ans(now,f[i-][x][y]);

        while(head<=tail&&now-pos[head]>l) head++;

        if(head<=tail) f[i][x][y]=q[head]+now;

        else f[i][x][y]=-inf;

        ans=max(ans,f[i][x][y]);

        x+=xi[d]; y+=yi[d]; now++;

    }

}

int main()

{

    int x,y,d,L;

    n=read(); m=read(); sx=read(); sy=read(); k=read();

    for(int i=;i<=n;i++) scanf("%s",a[i]+);

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

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

            f[][i][j]=-inf;

    f[][sx][sy]=;

    for(int i=;i<=k;i++){

        x=read(); y=read(); d=read(); L=y-x+;

        if(d==) for(int j=;j<=m;j++) dp(i,n,j,d,L);

        if(d==) for(int j=;j<=m;j++) dp(i,,j,d,L);

        if(d==) for(int j=;j<=n;j++) dp(i,j,m,d,L);

        if(d==) for(int j=;j<=n;j++) dp(i,j,,d,L);

    }

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

    return ;

}