6、数塔问题 【问题描述】 设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： 若要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。 【输入格式】 第一行为n(n<10)，表示数塔的层数 从第2行至n+1行，每行有若干个数据，表示数塔中的数值。 【输出格式】 输出路径和最大的路径值。 【输入样例】tower.in 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 【输出样例】tower.out 86
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN=101; int a[MAXN][MAXN]; int main() { int n; cin>>n; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) cin>>a[i][j]; } for(int i=n;i>1;i--) { for(int j=1;j<i;j++) a[i-1][j]=max(a[i][j],a[i][j+1])+a[i-1][j]; } cout<<a[1][1]<<endl; }