top1编程
← 返回题目
题解

【基础】数塔的行走路径

2 条题解

  • 0
    @ 2026-7-29 0:06:21
    #include <bits/stdc++.h>
    using namespace std;
    int n,a[1001][1001];
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=i;j++){
    			cin>>a[i][j];
    		}
    	}
    	for(int i=n-1;i>=1;i--){
    		for(int j=1;j<=i;j++){
    			if(a[i+1][j]>a[i+1][j+1]){
    				a[i][j]+=a[i+1][j];
    			}
    			else{
    				a[i][j]+=a[i+1][j+1];
    			}
    		}
    	}
    	int r[2000][10]={},i=1,j=1;
    	int k=1;
    	r[k][1]=1;
    	r[k][2]=1;
    	int h=n-1;
    	while(h--){
    		if(a[i+1][j]>a[i+1][j+1]){
    			r[++k][1]=i+1;
    			r[k][2]=j;
    			i++;
    		}
    		else{
    			r[++k][1]=i+1;
    			r[k][2]=j+1;
    			i++;
    			j++;
    		}
    	}
    	for(int i=k;i>=2;i--){
    		cout<<r[i][1]<<","<<r[i][2]<<"->";
    	}
    	cout<<"1,1"<<endl<<a[1][1];
    }
    
    • 0
      @ 2026-7-28 22:44:43
      #include <bits/stdc++.h>
      using namespace std;
      int a[110][110],b[110][110];
      int n,i,j,k;
      int main(){
      	cin>>n;
      	for(i=1;i<=n;i++){
      		for(j=1;j<=i;j++){
      			cin>>a[i][j];
      		}
      	}
      	for(i=n-1;i>=1;i--){
      		for(j=1;j<=i;j++){
      			a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
      		}
      	}
      	k=1;
      	b[1][1]=1;//行下标
      	b[1][2]=1;//列下标
      	i=1;
      	j=1;
      	while(i<n){
      		k++;
      		if(a[i+1][j]>a[i+1][j+1]){
      			b[k][1]=i+1;
      			b[k][2]=j;
      			i++;
      		}
      		else{
      			b[k][1]=i+1;
      			b[k][2]=j+1;
      			i++;
      			j++;
      		}
      	}
      	for(int i=k;i>=1;i--){
      		cout<<b[i][1]<<","<<b[i][2];
      		if(i!=1){
      			cout<<"->";
      		}
      	}
      	cout<<endl<<a[1][1];
      	return 0;
      }
      
      • 1