3262新数字三角形

3262新数字三角形

描述

图1给出了一个数字三角形。
从指定的一个数往下走，可以走到下一层上和它最近的左边的那个数或者右边的那个数。

任务

：
给定数字三角形中的一个位置，求从它开始所能到达的最大数。

输入

输入数据包含多组测试数据，

对于每组测试数据：
输入的第一行是一个整数N (0 <= N <= 100)，给出三角形的行数。
（当N为0时，表示测试结束，你不需要处理本组数据）
下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
接下来一行有两个数,R和C，表示起始点位于第R行第C个位置。

输出

输出若干行，每行对应一组测试数据的结果。

样例输入

1
2
1 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
1 1
6
88
97 26
39 16 47
94 25 66 4
64 49 20 36 27
37 87 29 37 10 40
2 1
0

样例输出

2
8
97
递推，注意不是求和的最大值，是求经过的单值的最大值。

#include<iostream>
#include<algorithm> 
#include<cstring>
using namespace std;
int a[120][120];
int maxsum[120][120];
int main()
{int n,max_low;while(cin>>n&&n){memset(maxsum,0,sizeof(maxsum));memset(a,0,sizeof(a));int x,y;for(int i=1;i<=n;i++)//读入数字三角形 for(int j=1;j<=i;j++)cin>>a[i][j];cin>>x>>y;//读入位置 for(int i=n,j=1;j<=n;j++)//最后一层 maxsum[i][j]=a[i][j];for(int i=n-1;i>=1;i--)//递推找最大值 for(int j=1;j<=i;j++){max_low= max(maxsum[i+1][j],maxsum[i+1][j+1]);//底层两个中的最大 maxsum[i][j]=max(max_low,a[i][j]);//底层最大与当前位置值的最大 }cout<<maxsum[x][y]<<endl;//输入相应位置最大值 }return 0;
}