震惊！这跟我想的不太一样？！

许凉城 @ 2018-10-14 20:37:06

#include <bits/stdc++.h>//在dfs里dp 
using namespace std;
int x[4]={0,-1,0,1},
    y[4]={1,0,-1,0};
int a[105][105]={0},b[105][105]={0};
int r,c,maxx=-1;
int max(int x,int y)
{
    if (x>=y) return x;
    else return y;
}
int dfs(int p,int q)
{
    if (b[p][q]>0)
    {
        return (b[p][q]+1);
    }
    int tp,tq;
    for (int i=0;i<4;i++)   
    {
        tp=p+x[i];tq=q+y[i];
        if (1<=tp && tp<=r && 1<=tq && tq<=c && a[tp][tq]<a[p][q])
        {
            b[p][q]=max(b[p][q],dfs(tp,tq));
        }
    }
}
int main()
{
    cin>>r>>c;
    for (int i=1;i<=r;i++)
    {
        for (int j=1;j<=c;j++)
        {
            cin>>a[i][j];
        }
    }
    for (int i=1;i<=r;i++)
    {
        for (int j=1;j<=c;j++)      
        {
            b[i][j]=max(1,dfs(i,j));
            //cout<<b[i][j]<<" ";
        }
        //cout<<endl;
    }
    for (int i=1;i<=r;i++)
    {
        for (int j=1;j<=c;j++)
        {
            if (maxx<b[i][j])
            {
                maxx=b[i][j];
            }
            //cout<<b[i][j]<<" ";
        }
        //cout<<endl;
    }
    cout<<maxx;
    return 0;
}

by tylon2006 @ 2018-10-14 22:13:47

@许凉城

emmm...您写的是记忆化搜索

dfs部分改为

int dfs(int p,int q)
{
    if (b[p][q]>0)
    {
        return b[p][q];
    }
    int tp=0,tq=0;
    for (int i=0;i<4;i++)   
    {
        tp=p+x[i];tq=q+y[i];
        if (1<=tp && tp<=r && 1<=tq && tq<=c && a[tp][tq]<a[p][q])
        {
            b[p][q]=max(b[p][q],dfs(tp,tq)+1);
        }
    }
    return b[p][q];
}

maxx请赋值为1（保险）

然而这部分并没有什么卵用

  for (int i=1;i<=r;i++)
    {
        for (int j=1;j<=c;j++)      
        {
            b[i][j]=max(1,dfs(i,j));
            //cout<<b[i][j]<<" ";
        }
        //cout<<endl;
    }

主程序可以改成

int main()
{
    cin>>r>>c;
    for (int i=1;i<=r;i++)
    {
        for (int j=1;j<=c;j++)
        {
            cin>>a[i][j];
        }
    }
    for (int i=1;i<=r;i++)
    {
        for (int j=1;j<=c;j++)      
        {
            maxx=max(maxx,dfs(i,j)+1);
            //cout<<b[i][j]<<" ";
        }
        //cout<<endl;
    }
    cout<<maxx;
    return 0;
}
````cpp

by tylon2006 @ 2018-10-14 22:15:48

为何您的dfs最后不return b[p][q]

吓得我以为我搞炸了

by tylon2006 @ 2018-10-14 22:17:10

想起我一年前做这题的黑暗回忆...

by tylon2006 @ 2018-10-15 12:26:31

@许凉城

by 许凉城 @ 2018-10-15 19:01:05

@tylon2006好......我的错/笑哭 大感谢！！！