View Code of Problem 65

#include <iostream>
#include <cstring>
using namespace std;
int a[1010][1010],dp[1010][1010];
int main(){
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			for(int j=n-(i-1);j<=n+(i-1);j+=2){
				cin>>a[i][j];
			}
		}
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=2*n-1;j++){
//				cout<<a[i][j];
//			}
//			cout<<endl;
//		}
		dp[1][n]=a[1][n];
		for(int i=2;i<=n;i++){
			for(int j=n-(i-1);j<=n+(i-1);j+=2){
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j+1])+a[i][j];
			}
		}
		int res=a[1][n];
		for(int i=1;i<=2*n-1;i+=2){
			res=max(res,dp[n][i]);
		}
		cout<<res<<endl;
		memset(a,0,sizeof(a));
		memset(dp,0,sizeof(dp));
	}
	return 0;
}