题解洛谷 P2254 【[NOI2005]瑰丽华尔兹】

发现在同一时间段中，滑动的方向具有唯一性，所以不难得出\(DP\)方程。

\(f_{i,j}=max(f_{i,j},f_{i-dx_,j-dy}+dis_{i,j,i-dx_,j-dy})\)

\((i,j)\)为坐标，\((i-dx_,j-dy)\)为可以转移到\((i,j)\)的合法坐标，\(dis\)为计算两个坐标之间移动的距离。

继续考虑滑动的方向具有唯一性这一特点，也就是钢琴只能在行上或列上滑动一个固定的区间范围，不难想到滑动窗口这一模型。于是采用单调队列优化\(DP\)，每次只从队头转移，也就是每次都是从合法区间中选取了最优的状态转移过来。

时间复杂度为\(O(knm)\)。

其他细节处理就看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 310

#define inf 200000000

using namespace std;

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag)x=-x;

}

int n,m,x,y,k,f,r,ans;

char w[maxn][maxn];

int dp[maxn][maxn],dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

struct que

{

    int val,x,y;

}q[maxn];

int dis(int ax,int ay,int bx,int by)

{

    return abs(ax-bx)+abs(ay-by);

}

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

{

    f=1,r=0,d--;

    while(1)

    {

        if(x<1||y<1||x>n||y>m) break;

        if(w[x][y]=='x') f=1,r=0;

        else

        {

            while(f<=r&&dp[x][y]>q[r].val+dis(x,y,q[r].x,q[r].y)) r--;

            q[++r]=(que){dp[x][y],x,y};

            while(f<=r&&(abs(x-q[f].x)>len||abs(y-q[f].y)>len)) f++;

            dp[x][y]=max(dp[x][y],q[f].val+dis(x,y,q[f].x,q[f].y));

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

        }

        x+=dx[d],y+=dy[d];

    }

}

int main()

{

	read(n),read(m),read(x),read(y),read(k);

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

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

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

            dp[i][j]=-inf;

    dp[x][y]=0;

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

    {

        int s,t,l,d;

        read(s),read(t),read(d),l=t-s+1;

        if(d==1) for(int j=1;j<=m;++j) work(n,j,l,d);

        if(d==2) for(int j=1;j<=m;++j) work(1,j,l,d);

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

        if(d==4) for(int j=1;j<=n;++j) work(j,1,l,d);

    }

    printf("%d",ans);

	return 0;

}

巴特西

题解洛谷 P2254 【[NOI2005]瑰丽华尔兹】

最新文章

热门文章

巴特西

题解 洛谷 P2254 【[NOI2005]瑰丽华尔兹】

最新文章

热门文章

题解洛谷 P2254 【[NOI2005]瑰丽华尔兹】