BZOJ1499：[NOI2005]瑰丽华尔兹—

http://www.lydsy.com/JudgeOnline/problem.php?id=1499

　　舞厅是一个N行M列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。

　　艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长，这样1900 会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。

……其实这是单调队列优化吧……

我们有一个显然的f[i][j][k]表示在i时间段内钢琴到(j,k)处时最大移动距离。

显然f可以很简单的转移，但是复杂度会爆炸。

但是又显然可以对每个点单调队列优化……

而且既然不是斜率优化，所以单调队列的维护也很简单，直接看代码吧。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

const int T=;

const int N=;

inline int read(){

    int X=,w=;char ch=;

    while(ch<''||ch>''){if(ch=='-')w=-;ch=getchar();}

    while(ch>=''&&ch<='')X=(X<<)+(X<<)+ch-'',ch=getchar();

    return X*w;

}

int f[T][N][N],qx[N],qy[N];

char s[N];

bool ok[N][N];

int dx[]={,-,,,};

int dy[]={,,,-,};

struct time{

    int t,d;

}p[T];

int n,m;

void dp(int x,int y,int k){

    int l=,r=;

    while(x>=&&y>=&&x<=n&&y<=m){

        while(l<r&&abs(x-qx[l])+abs(y-qy[l])>p[k].t)l++;

        while(l<r&&!ok[x][y])r--;

        while(l<r){

            int t1=f[k-][qx[r-]][qy[r-]]+abs(x-qx[r-])+abs(y-qy[r-]);

            int t2=f[k-][x][y];

            if(t1<t2)r--;

            else break;

        }

        if(ok[x][y]){

            qx[r]=x,qy[r++]=y;

            f[k][x][y]=f[k-][qx[l]][qy[l]]+abs(x-qx[l])+abs(y-qy[l]);

        }

        x+=dx[p[k].d];y+=dy[p[k].d];

    }

}

int main(){

    n=read(),m=read();

    int x=read(),y=read(),t=read();

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

        scanf("%s",s+);

        for(int j=;j<=m;j++)ok[i][j]=(s[j]=='.');

    }

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

    f[][x][y]=;

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

        int t1=read(),t2=read();

        p[i].t=t2-t1+;p[i].d=read();

    }

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

        if(p[k].d==)

            for(int j=;j<=m;j++)dp(n,j,k);

        if(p[k].d==)

            for(int j=;j<=m;j++)dp(,j,k);

        if(p[k].d==)

            for(int i=;i<=n;i++)dp(i,m,k);

        if(p[k].d==)

            for(int i=;i<=n;i++)dp(i,,k);

    }

    int ans=;

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

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

            ans=max(ans,f[t][i][j]);

        }

    }

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

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ1499：[NOI2005]瑰丽华尔兹——题解

最新文章

热门文章