0w1

TIOJ 1170 . 競技場 (Arena) ( DP )

1170 - 競技場 (Arena) | TIOJ INFOR Online Judge
dp[ i ][ j ] : 考慮 [ i, j ] 區間時,最大的獲益
dp[ i ][ j ] = max{ max( dp[ i ][ m ], dp[ m + 1 ][ j ] ) + sum( i, m ) * sum( m + 1, j ) | for all i ≤ m and m + 1 ≤ j }
sum( i, j ) = sum of values in range [ i, j ]

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef pair< int, int > pii;
typedef vector< pii > vp;

const int INF = 0x3f3f3f3f;

int N;
vi A;
vi pA;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    pA = vi( N + 1 );
    for( int i = 0; i < N; ++i )
        pA[ i + 1 ] = pA[ i ] + A[ i ];
}

int get_f( int ql, int mid, int qr ){ // [ ql, mid ], [ mid + 1, qr ]
    ++ql, ++mid, ++qr;
    return ( pA[ mid ] - pA[ ql - 1 ] ) * ( pA[ qr ] - pA[ mid ] );
}

void solve(){
    vvi dp( N, vi( N, -INF ) );
    for( int i = 0; i < N; ++i )
        dp[ i ][ i ] = 0;
    for( int k = 2; k <= N; ++k )
        for( int i = 0; i < N; ++i ){
            int j = i + k - 1;
            if( j >= N )
                break;
            for( int t = i; t + 1 <= j; ++t )
                dp[ i ][ j ] = max( dp[ i ][ j ], max( dp[ i ][ t ], dp[ t + 1 ][ j ] ) + get_f( i, t, j ) );
        }
    cout << dp[ 0 ][ N - 1 ] << endl;
}

signed main(){
    ios::sync_with_stdio( false );
    init();
    solve();
    return 0;
}