【bzoj1499】 NOI2005—瑰丽华尔兹

时间：2022-12-29 22:22:02

http://www.lydsy.com/JudgeOnline/problem.php?id=1499 (题目链接)

题意

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

Solution

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

代码

// bzoj1499

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=300;

int xx[]={0,-1,1,0,0},yy[]={0,0,0,-1,1};

int q[maxn],p[maxn],f[2][maxn][maxn];

int n,m,L,ans,X,Y,K;

char a[maxn][maxn];

void dp(int d,int x,int y,int t) {

    int l=1,r=0,cnt=1;

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

        if (a[x][y]=='x') l=1,r=0;

        while (l<=r && cnt-p[l]>L) l++;

        while (l<=r && q[r]+cnt<f[d^1][x][y]) r--;

        q[++r]=f[d^1][x][y]-cnt;p[r]=cnt;

        if (l>r) f[d][x][y]=-inf;

        else f[d][x][y]=q[l]+cnt;

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

        cnt++;

        x+=xx[t];y+=yy[t];

    }

}

int main() {

    scanf("%d%d%d%d%d",&n,&m,&X,&Y,&K);

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

    for (int i=0;i<=1;i++)

        for (int j=1;j<=n;j++)

            for (int k=1;k<=m;k++) f[i][j][k]=-inf;

    int d=0;f[0][X][Y]=0;

    for (int u,v,t,i=1;i<=K;i++) {

        d^=1;

        scanf("%d%d%d",&u,&v,&t);

        L=v-u+1;

        if (t==1) for (int j=1;j<=m;j++) dp(d,n,j,t);

        if (t==2) for (int j=1;j<=m;j++) dp(d,1,j,t);

        if (t==3) for (int j=1;j<=n;j++) dp(d,j,m,t);

        if (t==4) for (int j=1;j<=n;j++) dp(d,j,1,t);

    }

    printf("%d",ans);

    return 0;

}

　　

相关文章