【BZOJ1499】瑰丽华尔兹（动态规划）

题面

题解

先写部分分

设\(f[t][i][j]\)表示当前在\(t\)时刻，位置在\(i,j\)时走的最多的步数

这样子每一步要么停要么走

时间复杂度\(O(nmt)\)

得分\(40~70\)分

（据说这样能过？？？）

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 210

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

char g[MAX][MAX];

int ans,n,m,X,Y,K,L[MAX],R[MAX],D[MAX];

int d[5][2]={0,0,-1,0,1,0,0,-1,0,1};

int f[2][MAX][MAX],T[MAX*MAX];

int main()

{

	n=read();m=read();X=read();Y=read();K=read();

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

	for(int i=1;i<=K;++i)L[i]=read(),R[i]=read(),D[i]=read();

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

		for(int j=L[i];j<=R[i];++j)T[j]=D[i];

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

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

	int nw=1,pw=0;

	for(int tt=1;tt<=R[K];++tt,nw^=1,pw^=1)

	{

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

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

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

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

			{

				if(f[pw][i][j]==-1)continue;

				int xx=i+d[T[tt]][0],yy=j+d[T[tt]][1];

				f[nw][i][j]=max(f[nw][i][j],f[pw][i][j]);

				if(xx<1||yy<1||xx>n||yy>m)continue;

				if(g[xx][yy]=='x')continue;

				f[nw][xx][yy]=max(f[nw][xx][yy],f[pw][i][j]+1);

			}

	}

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

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

			ans=max(ans,f[R[K]&1][i][j]);

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

	return 0;

}

发现转移可以用单调队列优化

于是分四种情况进行讨论

用单调队列优化转移即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 210

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

char g[MAX][MAX];

int ans,n,m,X,Y,K,L[MAX],R[MAX],D[MAX];

int d[5][2]={0,0,-1,0,1,0,0,-1,0,1};

int f[2][MAX][MAX],T[MAX*MAX];

int Q[MAX],h,t;

int main()

{

	n=read();m=read();X=read();Y=read();K=read();

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

	for(int i=1;i<=K;++i)L[i]=read(),R[i]=read(),D[i]=read();

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

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

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

	int nw=1,pw=0;

	for(int tt=1;tt<=K;++tt,nw^=1,pw^=1)

	{

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

			for(int j=1;j<=m;++j)f[nw][i][j]=f[pw][i][j];

		if(D[tt]==1)

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

			{

				h=1;t=0;

				for(int i=n;i;--i)

				{

					if(g[i][j]=='x'){h=1;t=0;continue;}

					while(h<=t&&Q[h]-i>R[tt]-L[tt]+1)++h;

					while(h<=t&&f[pw][Q[t]][j]+Q[t]<=f[pw][i][j]+i)--t;

					Q[++t]=i;

					if(h<=t)f[nw][i][j]=f[pw][Q[h]][j]+Q[h]-i;

				}

			}

		else if(D[tt]==2)

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

			{

				h=1;t=0;

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

				{

					if(g[i][j]=='x'){h=1;t=0;continue;}

					while(h<=t&&i-Q[h]>R[tt]-L[tt]+1)++h;

					while(h<=t&&f[pw][Q[t]][j]-Q[t]<=f[pw][i][j]-i)--t;

					Q[++t]=i;

					if(h<=t)f[nw][i][j]=f[pw][Q[h]][j]+i-Q[h];

				}

			}

		else if(D[tt]==3)

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

			{

				h=1;t=0;

				for(int j=m;j;--j)

				{

					if(g[i][j]=='x'){h=1;t=0;continue;}

					while(h<=t&&Q[h]-j>R[tt]-L[tt]+1)++h;

					while(h<=t&&f[pw][i][Q[t]]+Q[t]<=f[pw][i][j]+j)--t;

					Q[++t]=j;

					if(h<=t)f[nw][i][j]=f[pw][i][Q[h]]+Q[h]-j;

				}

			}

		else

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

			{

				h=1;t=0;

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

				{

					if(g[i][j]=='x'){h=1;t=0;continue;}

					while(h<=t&&j-Q[h]>R[tt]-L[tt]+1)++h;

					while(h<=t&&f[pw][i][Q[t]]-Q[t]<=f[pw][i][j]-j)--t;

					Q[++t]=j;

					if(h<=t)f[nw][i][j]=f[pw][i][Q[h]]+j-Q[h];

				}

			}

	}

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

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

			ans=max(ans,f[K&1][i][j]);

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

	return 0;

}

巴特西

【BZOJ1499】【NOI2005】瑰丽华尔兹（动态规划）

【BZOJ1499】瑰丽华尔兹（动态规划）

题面

题解

最新文章

热门文章