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; }