问题标题: 酷町堂：4972

20分错误代码：

#include<iostream>
using namespace std;
int f[9],n,a[15][15],sum,pos=1;
int dfs(){
    for(int i=1;i<=n;i++){
        int maxn=0;
        if(pos>i)break;
        for(int j=pos;j<=i;j++){
            if(a[i][j]+a[i+1][j-1]>f[i]){
                f[i]=a[i][j]+a[i+1][j-1];
                maxn=a[i][j];
                pos=j-1;
            }
            if(a[i][j]+a[i+1][j+1]>f[i]){
                f[i]=a[i][j]+a[i+1][j+1];
                maxn=a[i][j];
                pos=j+1;
            }
        }
        sum+=maxn;
    }
    return sum;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    cout<<dfs();
    return 0;
}

 

张皓轩在2021-09-20 16:03:48追加了内容

20分：

#include<iostream>

using namespace std;

int f[15][15],n,a[15][15],sum,pos=1;

int f1(){

for(int i=n;i>=1;i--){

for(int j=1;j<=i;j++){

f[i][j]=max(f[i+1][j]+a[i][j],f[i+1][j-1]+a[i][j]);

}

}

return f[n][n];

}

int main(){

cin>>n;

for(int i=1;i<=n;i++){

for(int j=1;j<=i;j++){

cin>>a[i][j];

f[i][j]=a[i][j];

}

}

cout<<f1();

return 0;

}