1 #include<stdio.h> 2 #include<string.h> 3 const int maxm=500+5,maxn=1000+5; 4 int d[maxm][maxn],a[maxm][maxn],n; 5 int trimax(int x,int y,int z) 6 { 7     int maxnum=x; 8     if(maxnum<y) 9         maxnum=y;10     if(maxnum<z)11         maxnum=z;12     return maxnum;13 }14 int dp(int i,int j);15 int main()16 {17     int t;18     scanf("%d",&t);19     while(t--){20         scanf("%d",&n);21         for(int i=1;i<=n;i++)22         for(int j=1;j<=2*i-1;j++)23         scanf("%d",&a[i][j]);24         memset(d,-1,sizeof(d));25         int ans=dp(1,1);26         printf("%d\n",ans);27     }28     return 0;29 }30 int dp(int i,int j)31 {32     if(d[i][j]>=0)33         return d[i][j];34     if(i==n)35         return d[i][j]=a[i][j];36     return d[i][j]=a[i][j]+trimax(dp(i+1,j),dp(i+1,j+1),dp(i+1,j+2));37 }