记忆数 组全局变量初始化TLE啊 但-1就过了

RingTouSou @ 2023-10-07 00:40:01

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N][N],f[N][N];
int dfs(int x,int y)
{
    if(f[x][y]!=-1)
    {
        return f[x][y];//记忆化搜索
    }
    if(x==n)
    {
        return f[x][y]=a[x][y];  //到边界直接取
    }
    return f[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];
    //记录左右哪个大并取  加上自身
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }
    memset(f,-1,sizeof(f));
    dfs(1,1);
    cout<<f[1][1];
}

by RingTouSou @ 2023-10-07 00:40:40

用memset初始化成0也是错的？不能初始化为0吗

by Jianbing_Juan @ 2023-10-07 01:36:30

@RingTouSou memset() 函数，第二个参数应该改成 false .

另外建议用数组直接转移状态，不然容易挂。

by xiaoming007 @ 2023-10-07 06:27:37

@Jianbing_Juan 你谁？你见过初始 -1 谁家 memset 改成 false 的？

by xiaoming007 @ 2023-10-07 06:29:59

@RingTouSou 数组全是 0 你这个记忆化不就退化成爆搜了。

by RingTouSou @ 2023-10-07 16:11:43

@xiaoming007 为啥啊 我全是0然后后面赋值记忆道这个数组 然后不是0就return 不是记忆化？ 要存的值不可能为0啊

by Jianbing_Juan @ 2023-10-07 18:59:40

@xiaoming007 我错了，我库函数没学好。

那如果要初始化为-1的话应该不能用 memset 吧。

我只知道用 for循环初始化为-1的方法。

by xiaoming007 @ 2023-10-07 21:57:10

@Jianbing_Juan 可以初始-1的

by xiaoming007 @ 2023-10-07 21:58:13

@RingTouSou 哥，你考虑所有 a_{x,y} 都是 0 的情况你这代码就跑不动了。你的记忆化减不了这个的枝。

by RingTouSou @ 2023-10-07 23:47:02

@xiaoming007 佬对不起... 但在这个数组中不会出现0的情况啊 a【x】【y】是0但是它不考虑啊 不是只有边界的时候才考虑嘛...f[x][y]在界内不会出现0啊 刚刚学有点没太懂....也没人讲

by Jianbing_Juan @ 2023-10-08 00:08:04

@xiaoming007 对，我是蒟蒻。

我脑抽了，麻烦您了

感觉我像是猴子

%%%