55分 一会tel一会re 求助dalao

老y万人敬仰。 @ 2018-07-15 11:13:46

#include<iostream>
#include<cstdio>
using namespace std;
int  a[100][1000],R,s=0,ans=-999999;
void dfs(int x,int y)
{
    s=s+a[x][y];
    if(x==R)
    {
        if(ans<s) ans=s;
    }
    else
        for(int i=0;i<=1;i++)
            dfs(x+1,y+i);
    s=s-a[x][y];
}
int main()
{
    cin>>R;
    for(int i=1;i<=R;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    dfs(1,1);
    cout<<ans;
    return 0;
}

by andyli @ 2018-07-15 11:15:12

@yangyibangyi tel是什么鬼

by andyli @ 2018-07-15 11:15:57

@yangyibangyi 这题是动态规划呀，不是深搜

by andyli @ 2018-07-15 11:16:24

@yangyibangyi 你看我代码：

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1050;

int A[maxn][maxn], d[maxn][maxn];
int n;

int dp(int i, int j)
{
    if (d[i][j] >= 0)
        return d[i][j];
    return d[i][j] = A[i][j] + (i == n ? 0 : max(dp(i + 1, j), dp(i + 1, j + 1)));
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> A[i][j];
    memset(d, -1, sizeof(d));
    cout << dp(1, 1) << endl;
    return 0;
}

by 初音Miku @ 2018-07-15 11:17:49

搜索的话你需要记忆化搜索，不然肯定超时喽

by 老y万人敬仰。 @ 2018-07-15 11:22:21

@初音Miku 好的 谢谢！

by 老y万人敬仰。 @ 2018-07-15 11:22:32

@andyli 感谢！！！

by Victory_Defeat @ 2018-07-15 12:27:30

tel是什么鬼？

by 2017gdgzoi999 @ 2018-12-21 20:28:33

#define tel TLE