对于记忆化搜索类的高级算法(复杂的递归)怎么调试
  • 板块学术版
  • 楼主heike305
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/12/19 16:54
  • 上次更新2023/10/24 07:12:04
查看原帖
对于记忆化搜索类的高级算法(复杂的递归)怎么调试
789739
heike305楼主2022/12/19 16:54

rt

不是一维的,而且函数递归多得很

例如下面这段代码(样例都没过,不是tlqtj)

#include <bits/stdc++.h>//用的记忆化搜索
using namespace std;
long long a[105][105],b[105][105],r,c;//初始化
int f(int x,int y,int num)
{
    if(a[x][y]<a[x-1][y]&&a[x][y]<a[x][y-1])
    if(a[x][y]<a[x][y+1]&&a[x][y]<a[x+1][y])
    return num+1;//若这是尽头,则返回,递归边界 
    if(b[x][y]!=-1)return b[x][y];//记忆化
    int ans=-1;
    if(a[x-1][y]<a[x][y])
    ans=max(f(x-1,y,num),ans)+1;
    if(a[x][y-1]<a[x][y])
    ans=max(f(x,y-1,num),ans)+1;
    if(a[x][y+1]<a[x][y])
    ans=max(f(x,y+1,num),ans)+1;
    if(a[x+1][y]<a[x][y])
    ans=max(f(x+1,y,num),ans)+1;//以上四行是找当前点的最优
    b[x][y]=ans;//记忆化
    return ans;
}
int main()
{
    for(int i=0;i<=102;i++)
    for(int j=0;j<=102;j++)
    {
        a[i][j]=21000000;//在地图外面建立一个高高的围墙,方便上面的递归边界 
        b[i][j]=-1;
    }//初始化
    cin >> r >> c;
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    cin >> a[i][j];//输入
    int ans=-1;
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    ans=max(ans,f(r,i,0));//枚举每个开头的点
    cout << ans;//输出
    return 0;
}

题目

2022/12/19 16:54
加载中...