lightoj 1004 - Monkey Banana Problem 【dp】

제목 링크: lightoj 1004 - Monkey Banana Problem
1004 - Monkey Banana Problem PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 32 MB You are in the world of mathematics to solve the great “Monkey Banana Problem”. It states that, a monkey enters into a diamond shaped two dimensional array and can jump in any of the adjacent cells down from its current position (see figure). While moving from one cell to another, the monkey eats all the bananas kept in that cell. The monkey enters into the array from the upper part and goes out through the lower part. Find the maximum number of bananas the monkey can eat.
Input Input starts with an integer T (≤ 50), denoting the number of test cases.
Every case starts with an integer N (1 ≤ N ≤ 100). It denotes that, there will be 2*N - 1 rows. The ith (1 ≤ i ≤ N) line of next N lines contains exactly i numbers. Then there will be N - 1 lines. The jth (1 ≤ j < N) line contains N - j integers. Each number is greater than zero and less than 215.
Output For each case, print the case number and maximum number of bananas eaten by the monkey.
Sample Input Output for Sample Input 2 4 7 6 4 2 5 10 9 8 12 2 2 12 7 8 2 10 2 1 2 3 1 Case 1: 63 Case 2: 5 Note Dataset is huge, use faster I/O methods.
제목: 2*N-1행을 정하고 수탑의 규정에 따라 하나의 노선을 걸어서 노선의 수를 최대로 하도록 요구한다.
사고방식: 우리가 중간의 출발점을 하나하나 들면, 이렇게 하면 쌍수탑이다.비합법적인 상태는 옮길 수 없으니 주의해라.
AC 코드:

//#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define PI acos(-1.0)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define fi first
#define se second
#define ll o<<1
#define rr o<<1|1
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 1e6 + 10;
const int pN = 1e6;// <= 10^7
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
void add(LL &x, LL y) { x += y; x %= MOD; }
LL a[110][110], b[110][110];
LL dp1[110][110], dp2[110][110];
int n;
LL Solve(int s) {
    CLR(dp1, 0); dp1[n][s] = a[n][s];
    for(int i = n-1; i >= 1; i-- ){
        for(int j = 1; j <= i; j++) {
            if(dp1[i+1][j+1] && dp1[i+1][j]) {
                dp1[i][j] = max(dp1[i+1][j+1], dp1[i+1][j]) + a[i][j];
            }
            else if(dp1[i+1][j+1]) {
                dp1[i][j] = dp1[i+1][j+1] + a[i][j];
            }
            else if(dp1[i+1][j]) {
                dp1[i][j] = dp1[i+1][j] + a[i][j];
            }
        }
    }
    CLR(dp2, 0); dp2[n][s] = b[n][s];
    for(int i = n-1; i >= 1; i--) {
        for(int j = 1; j <= i; j++) {
            if(dp2[i+1][j+1] && dp2[i+1][j]) {
                dp2[i][j] = max(dp2[i+1][j+1], dp2[i+1][j]) + b[i][j];
            }
            else if(dp2[i+1][j+1]) {
                dp2[i][j] = dp2[i+1][j+1] + b[i][j];
            }
            else if(dp2[i+1][j]) {
                dp2[i][j] = dp2[i+1][j] + b[i][j];
            }
        }
    }
    return dp1[1][1] + dp2[1][1] - a[n][s];
}
int main()
{
    int t, kcase = 1;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                scanf("%lld", &a[i][j]);
            }
        }
        for(int i = n; i >= 1; i--) {
            for(int j = 1; j <= i; j++) {
                if(i == n) {
                    b[i][j] = a[i][j];
                }
                else {
                    scanf("%lld", &b[i][j]);
                }
            }
        }
        LL ans = 0;
        for(int i = 1; i <= n; i++) {
            ans = max(ans, Solve(i));
        }
        printf("Case %d: %lld
", kcase++, ans);
    }
    return 0;
}