P2254

Aryper · 2021-09-22 19:57:53 · 个人记录

[NOI2005] 瑰丽华尔兹

这个数据范围很小啊，所以就可以单调队列优化这个 DP。

我们定义 f_k,_i,_j 为到第 k 个时间段结束时，位置在 (i,j) 的最大距离。

然后我们分时间段转移。

很显然，对于某一个固定的方向，这个在某一行或某一列，这个状态只能向固定的方向转移，而且转移的距离不能超过时间段的长度。于是我们就可以单调队列优化。

最后再处理一下这个障碍物。

然后没了。

时间复杂度 O(knm)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=2e2;

ll n,m,x,y,K,ans,h,t;

ll a[N+5][N+5],f[2][N+5][N+5],q[N+5];

ll s[N+5],_t[N+5],d[N+5];

char str[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();x=read();y=read();K=read();

    memset(f,-0x3f,sizeof(f));

    f[0][x][y]=0;

    for(ll i=1;i<=n;i++) {
        scanf("%s",str);
        for(ll j=0;j<m;j++) {
            if(str[j]=='.') a[i][j+1]=0;
            if(str[j]=='x') a[i][j+1]=1;
        }
    }

    for(ll i=1;i<=K;i++) {
        s[i]=read();_t[i]=read();d[i]=read();
    }

    for(ll i=1;i<=K;i++) {
        if(d[i]==1) {
            for(ll j=1;j<=m;j++) {
                h=1;t=0;
                for(ll k=n;k>=1;k--) {
                    if(a[k][j]==1) {
                        h=1;t=0;continue;
                    }
                    while(h<=t&&q[h]-k>_t[i]-s[i]+1) h++;
                    while(h<=t&&f[(i^1)&1][k][j]>f[(i^1)&1][q[t]][j]+q[t]-k) t--;
                    q[++t]=k;
                    if(h<=t) f[i&1][k][j]=f[(i^1)&1][q[h]][j]+q[h]-k;
                }
            }
        }
        if(d[i]==2) {
            for(ll j=1;j<=m;j++) {
                h=1;t=0;
                for(ll k=1;k<=n;k++) {
                    if(a[k][j]==1) {
                        h=1;t=0;continue;
                    }
                    while(h<=t&&k-q[h]>_t[i]-s[i]+1) h++;
                    while(h<=t&&f[(i^1)&1][k][j]>f[(i^1)&1][q[t]][j]+k-q[t]) t--;
                    q[++t]=k;
                    if(h<=t) f[i&1][k][j]=f[(i^1)&1][q[h]][j]+k-q[h];
                }
            }
        }
        if(d[i]==3) {
            for(ll j=1;j<=n;j++) {
                h=1;t=0;
                for(ll k=m;k>=1;k--) {
                    if(a[j][k]==1) {
                        h=1;t=0;continue;
                    }
                    while(h<=t&&q[h]-k>_t[i]-s[i]+1) h++;
                    while(h<=t&&f[(i^1)&1][j][k]>f[(i^1)&1][j][q[t]]+q[t]-k) t--;
                    q[++t]=k;
                    if(h<=t) f[i&1][j][k]=f[(i^1)&1][j][q[h]]+q[h]-k;
                }
            }
        }
        if(d[i]==4) {
            for(ll j=1;j<=n;j++) {
                h=1;t=0;
                for(ll k=1;k<=m;k++) {
                    if(a[j][k]==1) {
                        h=1;t=0;continue;
                    }
                    while(h<=t&&k-q[h]>_t[i]-s[i]+1) h++;
                    while(h<=t&&f[(i^1)&1][j][k]>f[(i^1)&1][j][q[t]]+k-q[t]) t--;
                    q[++t]=k;
                    if(h<=t) f[i&1][j][k]=f[(i^1)&1][j][q[h]]+k-q[h];
                }
            }
        }
    }

    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=m;j++) {
        //  printf("%lld ",f[K&1][i][j]);
            ans=max(ans,f[K&1][i][j]);
        }
    //  printf("\n");
    }

    write(ans);

    return 0;
}