题解

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