学步园

转载请注明出处谢谢：http://blog.csdn.net/vmurder/article/details/42888383

题解：

自己看数据范围分析一下就知道了，这题是有多水啊。

每次询问记忆化

每次修改单点暴力就好

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 705 
using namespace std;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

int map[N][N],f[N][N];
bool ok[N][N];
int n,m;
char opt[5];

int F(int x,int y)
{
	if(f[x][y])return f[x][y];
	for(int i=0;i<4;i++)
	{
		int tx=x+dx[i],ty=y+dy[i];
		if(!ok[tx][ty])continue;
		if(map[tx][ty]>=map[x][y])continue;
		f[x][y]=max(f[x][y],F(tx,ty));
	}
	return ++f[x][y];
}
int main()
{
	freopen("test.in","r",stdin);
	int i,j,k;
	int a,b,c,d;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%d",&map[i][j]);
			ok[i][j]=1;
		}
	}
	for(scanf("%d",&m);m--;)
	{
		scanf("%s",opt);
		if(opt[0]=='Q')
		{
			memset(f,0,sizeof f);
			int ans=0;
			for(i=1;i<=n;i++)for(j=1;j<=n;j++)
				if(ok[i][j])ans=max(ans,F(i,j));
			printf("%d\n",ans);
		}
		else if(opt[0]=='S')
		{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			for(i=a;i<=c;i++)for(j=b;j<=d;j++)ok[i][j]=0;
		}
		else if(opt[0]=='B')
		{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			for(i=a;i<=c;i++)for(j=b;j<=d;j++)ok[i][j]=1;
		}
		else {
			scanf("%d%d%d",&a,&b,&c);
			map[a][b]=c;
		}
	}
	return 0;
}