TLE求助!!!

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

Deric456 @ 2024-08-16 09:16:12

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define maxN 1005
int a[maxN][maxN],N,ans=0;
void Dfs(int x,int y,int CurrentValue){
    //终止条件
    if(x==N-1){
        if(CurrentValue>ans){
            ans=CurrentValue;       
        }
        return; 
    }
    Dfs(x+1,y,CurrentValue+a[x+1][y]);
    Dfs(x+1,y+1,CurrentValue+a[x+1][y+1]);
}
int main(){
    cin>>N;
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            cin>>a[i][j];
    Dfs(0,0,a[0][0]);
    cout<<ans<<endl;
    return 0;
}

by dmc0702 @ 2024-08-16 09:19:33

@Deric456 这道题要动态规划,普通搜索肯定超时


by dmc0702 @ 2024-08-16 09:22:28

记忆化搜索应该也行


by Deric456 @ 2024-08-16 09:39:11

@dmc0702 谢谢!AC了


|