7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(图一)
图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。
每一步只能由当前位置向左下或右下。
你的程序要能接受标准输入。第一行包含一个整数T，表示总的测试次数。
对于每一种情况：第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。
接下来的N行输入表示三角形的每一行的元素Ai,j，其中0 < Ai,j < 100。
输出每次测试的最大值并且占一行。
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
30
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main(void)
{int t;
cin>>t;
int i,j;
a[1]=1;
a[0]=0;
a[2]=1;
a[3]=2;
for(i=4;i<=40;i++)
{a[i]=a[i-1]+a[i-2];}
while(t--)
{int n;
cin>>n;
cout<<a[n]<<endl;
}
return 0;
}