请大佬帮忙看一下,TLE55分

Great_White_Shark @ 2024-05-27 21:36:49

#include <iostream>
using namespace std;
const int M=1500; //保证数组足够大
int a[M][M]; 
int ans=0; //初始化
int n;
void DFS(int x,int y,int sum){
    if(x==n+1){ //x到达最底层
        ans=max(ans,sum); //计算较大值
        return; //结束
    }
    DFS(x+1,y,sum+a[x+1][y]); //左下角
    DFS(x+1,y+1,sum+a[x+1][y+1]); //右下角
}
int main(){
    scanf("%d",&n); //已经变成scanf了
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            scanf("%d",&a[i][j]); //已经变成scanf了
        }
    }
    DFS(1,1,a[1][1]);
    printf("%d",ans); //已经变成printf了
}

by qazsedcrfvgyhnujijn @ 2024-05-27 22:33:01

先把你 DFS 否了，这题 r \le 1000，DFS的复杂度是（如果我没记错） \Theta(n!)，不 TLE 就是洛谷想关站了……
DP 不能不学啊……
可以发现，在一个特定点 u 接着往下走时的答案是一样的，也就是可以递推；
理论上来说这题可以记忆化搜索，就是记录已经算过的值；
然鹅，这题卡常，不写递推不行；
递推也不难写，给代码了：

#include <bits/stdc++.h>
using namespace std;
long long n, a[1005][1005];
main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); //取消 ios 和 stdio 的同步，以及 cin 和 cout 的绑定，可以使 cin/cout 和 scanf/printf 的速度相当
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    for (int i = n - 1; i >= 1; i--) //注意递推顺序
        for (int j = 1; j <= i; j++)
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
    cout << a[1][1];
}

下来自己在这个网页 动态规划基础 好好学一下 DP

by Great_White_Shark @ 2024-05-29 21:07:43

@qazsedcrfvgyhnujijn 拴Q

by Great_White_Shark @ 2024-05-30 21:00:02

@qazsedcrfvgyhnujijn 记忆化好像也可以诶.

#include <bits/stdc++.h>
using namespace std;
const int G=1010;

int A[G][G],B[G][G];
int N;

int DFS(int X,int Y){ //DFS()过程(记忆化)
    if(B[X][Y]==-1){ //若没计算过,(标注为-1)
        if(X==N) B[X][Y]=A[X][Y]; //已到底,直接计算(无需递归)
        else B[X][Y]=A[X][Y]+max(DFS(X+1,Y),DFS(X+1,Y+1)); //没到底,取较大值
    }
    return B[X][Y];
}

int main(){
  cin>>N;
  for(int I=1;I<=N;I++){
      for(int J=1;J<=I;J++){
          cin>>A[I][J];
      }
  }
  memset(B,-1,sizeof(B));
  DFS(1,1);
  cout<<B[1][1];
  return 0;
}

by Andyliu2023 @ 2024-07-03 21:35:07

什么DP啊

不如从下往上用递推

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

by Quartz_Blocks @ 2024-07-04 16:48:48

@Andyliu2023 这不就是dp吗

by Andyliu2023 @ 2024-07-14 10:54:10

@Quartz_Blocks 这是递推啊

by Quartz_Blocks @ 2024-07-14 10:58:05

@Andyliu2023 当我啥也没说

by Andyliu2023 @ 2024-07-15 13:02:32

@Quartz_Blocks 复杂非线性递推

by Luhaichuan @ 2024-07-20 09:45:56

@Great_White_Shark 这题不用dfs啊~