hdu2084
#include<algorithm> #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int data[105][105]; int temp[105][105]; /*int main()//从上往下 { int t; while(cin>>t) { while(t--) { int n; cin>>n; memset(data,0,sizeof(data)); for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { scanf("%d",&data[i][j]); } } temp[1][1]=data[1][1]; for(int i=2;i<=n;i++) { for(int j=1;j<=i;j++) { if(j==1) temp[i][j]=temp[i-1][j]+data[i][j]; if(j==i) temp[i][j]=temp[i-1][j-1]+data[i][j]; temp[i][j]=max(temp[i-1][j],temp[i-1][j-1])+data[i][j]; } } int m=0; for(int i=1;i<=n;i++) { if(m<temp[n][i]) m=temp[n][i]; } cout<<m<<endl; } } return 0; }*/ int main()//从下往上 { int t; while(cin>>t) { while(t--) { int n; cin>>n; memset(data,0,sizeof(data)); for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { scanf("%d",&data[i][j]); } } for(int i=1;i<=n;i++) { temp[n][i]=data[n][i]; } for(int i=n-1;i>=1;i--) { for(int j=1;j<=i;j++) { temp[i][j]=max(temp[i+1][j],temp[i+1][j+1])+data[i][j]; } } cout<<temp[1][1]<<endl; } } return 0; }