正式AFO @ 2018-11-07 22:15:37
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n, m, ans;
int mmap[1000][1000], member[1000][1000], vis[1000][1000];
void dfs(int x, int y, int cc){
int sum = cc;
int cnt = sum;
if(vis[x][y]) {sum += member[x][y];}
else{
if(x-1>=1&&mmap[x-1][y]<mmap[x][y]){
dfs(x-1, y, cc+1);
sum = max(sum, cnt+member[x-1][y]);
}
if(x+1<=n&&mmap[x+1][y]<mmap[x][y]){
dfs(x+1, y, cc+1);
sum = max(sum, cnt+member[x+1][y]);
}
if(y-1>=1&&mmap[x][y-1]<mmap[x][y]){
dfs(x, y-1, cc+1);
sum = max(sum, cnt+member[x][y-1]);
}
if(y+1<=m&&mmap[x][y+1]<mmap[x][y]){
dfs(x, y+1, cc+1);
sum = max(sum, cnt+member[x][y-1]);
}
}
vis[x][y] = 1;
member[x][y] = max(member[x][y], sum);
ans = max(ans, member[x][y]);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> mmap[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
dfs(i, j, 1);
cout << ans;
return 0;
} by 豊聡耳神子 @ 2018-11-07 22:28:27
请问楼主的cc是什么意思呢
by 豊聡耳神子 @ 2018-11-07 22:29:31
一般这题的记搜做法只用更新x和y的呢
by 豊聡耳神子 @ 2018-11-07 22:33:56
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int dp[110][110],n,m,a[110][110];//a为原蒟阵，dp为记忆化标记
int dfs(int,int);
int main()
{
int ans=0;
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
cin>>a[i][j];
dp[i][j]=1;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
ans=max(ans,dfs(i,j));//答案需要更新
cout<<ans;
return 0;
}
int dfs(int x,int y)
{
if(dp[x][y]!=1) return dp[x][y];//如果已被标记过，就直接返回
int p=0;
if(x>=1&&y>=1&&x<n&&y<=m&&a[x][y]>a[x+1][y]) p=max(p,(dfs(x+1,y)+1));//方向/判重
if(x>=1&&y>=1&&x<=n&&y<m&&a[x][y]>a[x][y+1]) p=max(p,(dfs(x,y+1)+1));
if(x>1&&y>=1&&x<=n&&y<=m&&a[x][y]>a[x-1][y]) p=max(p,(dfs(x-1,y)+1));
if(x>=1&&y>1&&x<=n&&y<=m&&a[x][y]>a[x][y-1]) p=max(p,(dfs(x,y-1)+1));
dp[x][y]=max(dp[x][y],p);//标记
return dp[x][y];//返回答案
}```
放上代码，供楼主参考吧