学步园

这个题经常被拿来当入门题呢，貌似以前做过。。。今天上午小白还给新人讲这个呢。

应该有两种做法吧，从上往下和从下往上推。

我还是喜欢用从上往下推。。

#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")

using namespace std;

const int MAX = 110;
int dp[MAX][MAX];
int a[MAX][MAX];

int main()
{
	int ncases,n;
	
	scanf("%d",&ncases);
	
	while( ncases-- )
	{
		scanf("%d",&n);
		for(int i=1; i<=n; i++)
			for(int k=1; k<=i; k++)
				scanf("%d",&a[i][k]);
		
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++)
			for(int k=1; k<=i; k++)
				dp[i][k] = max( dp[i-1][k-1], dp[i-1][k] ) + a[i][k];
				
		int ans = dp[n][max_element(dp[n]+1, dp[n]+n+1) - dp[n]];
		
		printf("%d\n",ans);
	}

return 0;
}