2wa求调

xXyhhyhhXX @ 2024-09-16 10:57:25

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

by szlyf2011 @ 2024-09-16 11:08:35

@xXyhhyhhXX

试试将第7行的for(int i=1;i<=t;i++)改为

for(int i=2;i<=t;i++)

by difficultlong @ 2024-09-16 11:39:34

@xXyhhyhhXX 对于金字塔的每行，dp[i][0] 和 dp[i][i] 只有一个上层元素可以到达，即 dp[i-1][0] 和 dp[i-1][i-1]。但您的代码将它们设置为 max(dp[i-1][0], dp[i-1][i-1])，你这里逻辑错误

你应该在更新 dp[i][j] 之前先更新 dp[i-1][j] 和 dp[i-1][j-1]，否则会使用到还未更新的值。

我认为（注意这是我的理解）在金字塔的最后一行找到最大的路径和，但最大的路径和应该是在每一步都累加的最大值。

by difficultlong @ 2024-09-16 11:42:35

@xXyhhyhhXX 如果你需要正确的代码，我这里提供一下：

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

    dp[1][1] = a[1][1];
    for (int i = 2; i <= t; i++) {
        for (int j = 1; j <= i; j++) {
            if (j == 1) {
                dp[i][j] = dp[i - 1][j] + a[i][j];
            } else if (j == i) {
                dp[i][j] = dp[i - 1][j - 1] + a[i][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
            }
        }
    }

    n = dp[t][1]; 
    for (int j = 2; j <= t; j++) {
        n = max(n, dp[t][j]);
    }

    cout << n << endl;
    return 0;
}

by difficultlong @ 2024-09-16 11:45:14

@xXyhhyhhXX 如果对你有帮助，求关注我非常的高兴

by xXyhhyhhXX @ 2024-09-16 11:52:11

@difficultlong 事实上，我是以dp[1][1]作为第一行第一列，而且不存在的上层元素未赋值为0，dp[i-1][i-1]必然大于dp[i-1][i]，所以这种做法是正确的。

by xXyhhyhhXX @ 2024-09-16 11:56:15

例：对于情况 dp[20][20]:

又因为 dp[19][19]>0，dp[19][20]=0\ 所以 \max(dp[19][19],dp[19][20])=dp[19][19]