0w1

IOI'94 The Triangle ( Easy DP )

PEG Judge - IOI '94 - The Triangle
感言:終於找到一個好 judge可以寫 ioi題了呢,雖然有點懷念錯過的 hoj。。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;

int n;
int tri[ MAXN ][ MAXN ];
int dp[ MAXN ][ MAXN ];
int ans;

void upmax(int &x, int v){
    if( x < v ) x = v;
    ans = max<int>( ans, x );
}

void solve(){
    dp[ 1 ][ 1 ] = tri[ 1 ][ 1 ];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j){
            upmax( dp[ i + 1 ][ j ], dp[ i ][ j ] + tri[ i + 1 ][ j ] );
            upmax( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] + tri[ i + 1 ][ j + 1 ] );
        }
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            scanf("%d", &tri[ i ][ j ]);
    solve();
    return 0;
}