TLE on#8

zhang_Jimmy @ 2023-07-08 10:51:09

#include<iostream>
using namespace std;
int a[1010][1010],s[1010][1010],n;
int f(int x,int y)
{
    if(s[x][y]) return s[x][y];
    if(x==n) return a[x][y];
    return s[x][y]=max(f(x+1,y),f(x+1,y+1))+a[x][y];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
        cin>>a[i][j];
    cout<<f(1,1);
}

by frogpig @ 2023-07-20 11:52:12

@zhangjingxing201228

这样搜可能超时吧

AC代码

#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int main(){
    int a;
    cin>> a;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=i;j++){
            cin>>dp[i][j];
        }
    }
    for(int i=a-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
        }
    }
    cout<<dp[1][1];
}

by blacksword @ 2023-07-21 14:47:36

我看了一下那个点的数据，全部都是0，如果按照这种方式记忆，就算是已经记忆过了，也会因为保存的值为0而被当作没有记忆。

by 1711Elegy @ 2023-08-13 17:03:46

@blacksword 谢谢，终于过了

我最开始也是直接用记忆化的数组看有没有访问

就#8TLE

如下

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
    x=0;int w=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}
struct Node{
    int data,l,r,deep;
}tree[1000000];
int num,n;
long shu(long n){
    if(n==1) return 1;
    return n*shu(n-1);
}
int k[10000000];
int ans(int x){
    if(tree[x].deep==n) return tree[x].data;
    else{
        if(k[x]) return k[x];
        else k[x]=tree[x].data+max(ans(tree[x].l),ans(tree[x].r));  
        return k[x];
    }
}
int main(){
    read(n);
    int x=0;
    for(int i=1;i<=n;i++){
        x+=i;
        for(int j=1;j<=i;j++){
            num++;
            read(tree[num].data);
            tree[num].l=x+j;
            tree[num].r=x+j+1;
            tree[num].deep=i;
        }
    }
    printf("%d",ans(1));
    return 0;
}

后来改成了单独的一个bool型数组看我这个结果有没有访问

如下

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
    x=0;int w=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}
struct Node{
    int data,l,r,deep;
}tree[1000000];
int num,n;
long shu(long n){
    if(n==1) return 1;
    return n*shu(n-1);
}
int k[10000000];
bool s[10000000];//该数组是后来增加的
int ans(int x){
    if(tree[x].deep==n) return tree[x].data;
    else{
        if(s[x]) return k[x];
        else{
            k[x]=tree[x].data+max(ans(tree[x].l),ans(tree[x].r));   
            s[x]=true;
            return k[x];
        }
    }
}
int main(){
    read(n);
    int x=0;
    for(int i=1;i<=n;i++){
        x+=i;
        for(int j=1;j<=i;j++){
            num++;
            read(tree[num].data);
            tree[num].l=x+j;
            tree[num].r=x+j+1;
            tree[num].deep=i;
        }
    }
    printf("%d",ans(1));
    return 0;
}

就AC了

by PanDaoxi @ 2023-08-23 20:46:41

其实记忆化数组初始化成 -1 就能解决上述问题。

// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 1e3 + 1;
int n, a[INF][INF], f[INF][INF];

int dfs(int i, int j){
    if(f[i][j] != -1) return f[i][j];
    if(i == n) return f[i][j] = a[i][j];
    else return f[i][j] = max(dfs(i+1, j), dfs(i+1, j+1)) + a[i][j];
}

int main(){
    ios :: sync_with_stdio(false);

    memset(f, -1, sizeof(f));
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin >> a[i][j];
        }
    }
    cout << dfs(1, 1);

    return 0;
}