用快读TLE,不用就AC?
  • 板块灌水区
  • 楼主西方不buy菌
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/11/21 22:15
  • 上次更新2023/11/5 07:33:58
查看原帖
用快读TLE,不用就AC?
372653
西方不buy菌楼主2020/11/21 22:15

AC:

#include<bits/stdc++.h>
using namespace std;
int dp[101][101],n,m,Map[101][101],dx[8]={0,1,0,-1},dy[8]={1,0,-1,0},ans=-0x7fffffff;
int dfs(int x,int y)
{
	if(x<0||y<0||x>=n||y>=m)
	{
		return 0;
	}
	if(dp[x][y])
	{
		return dp[x][y];
	}
	int mx=0;
	for(int i=0;i<4;i++)
	{
		if(Map[x+dx[i]][y+dy[i]]<Map[x][y])
		mx=max(mx,dfs(x+dx[i],y+dy[i]));
	}
	return dp[x][y]=mx+1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>Map[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			ans=max(ans,dfs(i,j));
		}
	}
	cout<<ans<<"\n";
}

TLE:

#include<bits/stdc++.h>
using namespace std;
inline int read()//整形的快读
{
	char ch;
	while((ch=getchar())<'0'||ch>'9');
	int res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')
	res=res*10+ch-48;
	return res;
}
int dp[101][101],n,m,Map[101][101],dx[8]={0,1,0,-1},dy[8]={1,0,-1,0},ans=-0x7fffffff;
int dfs(int x,int y)
{
	if(x<0||y<0||x>=n||y>=m)
	{
		return 0;
	}
	if(dp[x][y])
	{
		return dp[x][y];
	}
	int mx=0;
	for(int i=0;i<4;i++)
	{
		int tx=x+dx[i],ty=y+dy[i];
		if(Map[tx][ty]<Map[x][y])
		mx=max(mx,dfs(tx,ty));
	}
	return dp[x][y]=mx+1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			Map[i][j]=read();
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			ans=max(ans,dfs(i,j));
		}
	}
	cout<<ans<<"\n";
}

洛谷P1434

2020/11/21 22:15
加载中...