5681번: 공 쌓기

https://www.acmicpc.net/problem/5681


$O(tn^2)$

그대로 i행 j열 배열에 입력받는다.(계단 모양이 될 것이다.)
s[i][j]: j열의 1~i행 공들 점수합
dp[i][j]: 1~j-1열의 공들과 j열의 i행 이상의 공들을 적절히 선택해서 얻을 수 있는 최대 점수
dp[i][0]=0
dp[n][j]=dp[n-1][j-1]+s[n][j]
dp[i][j]=max(dp[i-1][j-1]+s[i][j],dp[i+1][j]) (0<=i<n)
dp[0][j]=max(0,dp[1][j])

답은 dp[0][n]

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int main() {
    while (scanf("%d", &n) && n) {
        int s[1002][1001] = { 0, };
        long long dp[1002][1001] = { 0, };
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                scanf("%d", &s[i][j]);
                s[i][j] += s[i - 1][j];
            }
        }
        for (int j = 1; j <= n; j++) {
            dp[n][j] = dp[n - 1][j - 1] + s[n][j];
            for (int i = n; --i;) dp[i][j] = max(dp[i - 1][j - 1] + s[i][j], dp[i + 1][j]);
            dp[0][j] = max(0LL, dp[1][j]);
        }
        printf("%lld\n", dp[0][n]);
    }
    return 0;
}