44分大佬求助QWQ

__Li_Chuan_Pei__ @ 2023-08-10 12:24:22

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

by _Fancy_ @ 2023-08-10 12:30:55

@Li_Chuan_Pei 转移方程的问题吧，给你一个参考

if(j != i)
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
else
    dp[i][j] = dp[i - 1][j - 1] + a[i][j];
ans = max(ans, dp[i][j]);

by __Shine__ @ 2023-08-10 12:56:15

@Li_Chuan_Pei

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

by __Li_Chuan_Pei__ @ 2023-08-10 19:42:12

@Shine ok

by __Li_Chuan_Pei__ @ 2023-08-10 19:42:46

@yutiti80 三克油