经典DP例子
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 110; int a[MAXN][MAXN],dp[MAXN][MAXN]; inline int Max(int a,int b){ return a>b?a:b; } int main(){ int c; while(~scanf("%d",&c)){ while(c--){ int n; scanf("%d",&n); memset(dp,0,sizeof(dp)); for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ scanf("%d",&a[i][j]); } } for(int i = n;i >= 1;i--){ for(int j = i;j >= 1;j--){ dp[i][j] = Max(dp[i+1][j],dp[i+1][j+1]) + a[i][j]; } } printf("%d\n",dp[1][1]); } } return 0; }