超时求助

nanami0721 @ 2024-08-06 10:37:01

#include<bits/stdc++.h>
using namespace std;
long long a[1010][1010],r;
long long dp(long long x,long long y,long long z){
    if(x>r){
        return 0;
    }
    z=a[x][y];
    z+=max(dp(x+1,y,z),dp(x+1,y+1,z));
    return z;
}
int main(){
    cin>>r;
    for(long long i=1;i<=r;i++){
        for(long long j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    cout<<dp(1,1,0);
}

by toolazy @ 2024-08-06 10:39:11

dp 用搜索要加记忆化...

by Ben_coding @ 2024-08-12 11:53:43

@Gmrys 这是一道动态规划的题目，动态规划的主要思想是递推，但是你用的的方法是递归，显然重复了多次运算操作，对于1000的数据量肯定会超时。

以下给出我的思路，仅供参考。

首先把数据都准备好，如下(为了实现动态规划，我们需要一个数组dp,dp[i][j]代表从第一行第一列走到第i行第j列)：

int r,a[1010][1010],dp[1010][1010];

接着把数据输进来：

scanf("%d",&r);
for (int i=1;i<=r;i++){
    for (int j=1;j<=i;j++){
        scanf("%d",&a[i][j]);
    }
}

接着是代码的核心部分，我们需要一个状态转移方程来实现动态规划。对于dp[i][j]，我们怎么求出它的值呢？根据题意，想要走到dp[i][j]，要么从dp[i-1][j]走过来，要么从dp[i-1][j-1]走过来。于是状态转移方程就自然而然地出来了：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]。

那么接下来我们只需要一个两重for循环，算出所有的dp[i][j]就可以了。其实这个操作和输入是可以同步的，所以上述代码可以改成这样:

scanf("%d",&r);
for (int i=1;i<=r;i++){
    for (int j=1;j<=i;j++){
        scanf("%d",&a[i][j]);
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
    }
}

代码到这里还没有完，根据题意，路线可以在底部的任意一个地方结束。所以还需要一个for循环，遍历dp数组底部的所有元素以找出最大值。

Max=dp[r][1];
for (int i=2;i<=r;i++){
    if (dp[r][i]>Max){
        Max=dp[r][i];
    }
}

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
int r,a[1010][1010],dp[1010][1010],Max;
int main(){
    scanf("%d",&r);
    for (int i=1;i<=r;i++){
        for (int j=1;j<=i;j++){
            scanf("%d",&a[i][j]);
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
        }
    }
    Max=dp[r][1];
    for (int i=2;i<=r;i++){
        if (dp[r][i]>Max){
            Max=dp[r][i];
        }
    }
    printf("%d",Max);
    return 0;
}