洛谷2254 BZOJ1499 瑰丽华尔兹题解

洛谷链接

BZ链接

一个很容易想到的做法就是用f[i][j][t]表示t时刻在i,j处的可以滑动的最大值

f[i][j][t]=max(f[i][j][t-1],f[*i][*j][t-1])，这样大力转移

只不过会TLE+MLE

所以我们要进行一下优化

f[i][j][k]表示在第k个时间段在i,j处的可以滑动的最大值

f[i][j][k]=max(f[*i][*j][k-1]+dis(i,j,*i,*j,f[i][j][k-1])

//*i,*j表示上一个合理的位置

注意到我们的i，与*i,以及j与*j一定有一个相等，即它们在同一行或者同一列

所以我们可以根据滑动的路径一行一行或者一列一列进行转移

而这个位置的可以转移来的位置即是它向前len长度的之内的位置

这与滑动窗口很类似，可以用单调队列来维护max(f[*i][*j][k-1])

然后在考虑障碍，我们发现一旦遇到障碍，之前的答案都不能转移过来

所以在有障碍是清空队列就好了

还有一个常规的优化，就是f[i][j][k]仅与f[i][j][k-1]有关，所以可以利用滚动数组进行优化

# include<iostream>

# include<cstdio>

# include<cmath>

# include<cstring>

# include<algorithm>

using namespace std;

const int mn = ;

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

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

struct node{int val,pos;};

node q[mn];

node make_node(int x,int y)

{

    node tmp;tmp.val=x,tmp.pos=y;

    return tmp;

}

int n,m,sx,sy,k;

int dp[mn][mn],ans,d;

char s[mn];

bool vis[mn][mn];

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

{

    int tail=,head=;

    for(int i=;x>= && x<=n && y>= && y<=m;i++,x+=dx[d],y+=dy[d])

    {

        if(!vis[x][y]) tail=,head=;

        else {

           while(tail<=head && q[head].val+i-q[head].pos<=dp[x][y]) head--;

           q[++head] = make_node(dp[x][y],i);//dp[x][y]实际上是dx[x][y][k-1]
　　　　　　　//BZOJ不支持c++11，写成q[++head]=node{dp[x][y],i}会CE

           while(tail<=head && q[head].pos-q[tail].pos>len) tail++;

           dp[x][y] = q[tail].val+i-q[tail].pos;//现在dp[x][y]才是dp[x][y][k]

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

        }

    }

}

int main()

{

    int x,y,z;

    scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&k);

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

    {

        scanf("%s",s+);

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

          if(s[j]=='.') vis[i][j]=;

          else vis[i][j]=;

    }

    memset(dp,0xf3,sizeof(dp));

    dp[sx][sy]=;

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

    {

        scanf("%d%d%d",&x,&y,&d);

        if(d==)

            for(int j=;j<=m;j++) work(n,j,y-x+);

        if(d==)

            for(int j=;j<=m;j++) work(,j,y-x+);

        if(d==)

            for(int j=;j<=n;j++) work(j,m,y-x+);

        if(d==)

            for(int j=;j<=n;j++) work(j,,y-x+);

    }

    printf("%d",ans);

    return ;

}

巴特西

洛谷2254 BZOJ1499 瑰丽华尔兹题解

最新文章

热门文章