题意概括
在N * N的矩阵中找到一条路径,使得路径上的数严格单调递减
题目分析
一眼N的范围很小很小,考虑搜索,暴力搜肯定会TLE,那么我们可以加一些玄学的优化
CODE
#include<bits/stdc++.h>
#define int long long //不开longlong见祖宗
const long long maxn=1e2+10;
int a[maxn][maxn],dp[maxn][maxn]; //dp[i][j] 表示走到(i,j)位置时最长路径的长度
int walk[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
using namespace std;
int n,m;
void DFS(int x,int y,int cnt)
{
if(x<1||x>n||y<1||y>n)return ;
if(dp[x][y]>=cnt) return ; // 如果曾经有更长的路径经过就没必要搜索了,因为同一个点进入几次都是等效的
dp[x][y]=cnt;
for(int i=0;i<=3;i++){
int new_x=x+walk[i][0];
int new_y=y+walk[i][1];
if(a[new_x][new_y] >= a[x][y])continue;
DFS(new_x,new_y,cnt+1);
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=INT_MIN; //初始化
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
DFS(i,j,1);
}
}
int ans=INT_MIN;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=max(ans,dp[i][j]); //寻找答案
}
}
cout<<ans;
return 0;
}
PS
对于搜索的题目,还有一种乱搞的方法,就是不要固定从(1,1)或者某个固定点开始DFS
你可以随机一个点,或者从(n,n)开始搜索
别小看这个玄学优化,碰到数据不是特别强的题就可以卡过去
比如:洛谷P1074(蓝题),我原本(1,1)开始搜索TLE几个点,但是从(9,1)开始搜就过了
虽然你可能有些原来AC的点用了这个方法后会T掉