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