题解
【基础】数塔的行走路径
2 条题解
-
0
#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
#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