lightoj1004

CODE

#include <iostream>

using namespace std;

int nCase,t,n;
int dp[205][105];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
            {
                scanf("%d", &dp[i][j]);
                dp[i][j] += max(dp[i-1][j-1], dp[i-1][j]);
            }
        for(int i = n + 1; i <= 2 * n - 1; i++)
            for(int j = 1; j <= 2 * n - i; j++)
            {
                scanf("%d", &dp[i][j]);
                dp[i][j] += max(dp[i-1][j], dp[i-1][j+1]);
            }
        printf("Case %d: %d\n", ++nCase, dp[2*n-1][1]);
    }
    return 0;
}