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