题目大意
题面还是比较好理解的。值得注意的是,如果取了中间一段,两边的会连成一段。
解题思路
两维的DP看起来是不行的。看到$n$只有$50$,我们 考虑升维。令$F[l][r][A][B]$表示在区间$[l,r]$中,取走一部分,剩余的最小为$A$,最大为$B$的代价;同时令$G[l][r]$表示取走$[l,r]$中所有所需要的代价。
那么我们有以下转移:
$$
F[l][r][\min(A,W[r])][max(B,W[r])]=min(F[l][k][A][B]+G[k+1][r-1])
$$
$$
G[l][r]=min(F[l][k][A][B]+a+b*(B-A)^2+G[k+1][r])
$$
最后$G[1][n]$就是答案。
参考程序
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 60;
int n, a, b, W[ Maxn ];
int F[ Maxn ][ Maxn ][ Maxn ][ Maxn ], G[ Maxn ][ Maxn ];
int Ref[ Maxn ];
void Upd( int &x, int y ) {
if( x == -1 || x > y ) x = y;
return;
}
int main() {
scanf( "%d", &n );
scanf( "%d%d", &a, &b );
for( int i = 1; i <= n; ++i )
scanf( "%d", &W[ i ] );
for( int i = 1; i <= n; ++i )
Ref[ i ] = W[ i ];
sort( Ref + 1, Ref + n + 1 );
for( int i = 1; i <= n; ++i )
W[ i ] = lower_bound( Ref + 1, Ref + n + 1, W[ i ] ) - Ref;
memset( G, 255, sizeof( G ) );
memset( F, 255, sizeof( F ) );
for( int i = 1; i <= n; ++i )
G[ i ][ i ] = a;
for( int i = 1; i <= n; ++i )
F[ i ][ i ][ W[ i ] ][ W[ i ] ] = 0;
for( int Len = 2; Len <= n; ++Len )
for( int i = 1; i + Len - 1 <= n; ++i ) {
int j = Len + i - 1;
for( int k = i; k < j - 1; ++k )
for( int A = 1; A <= n; ++A )
for( int B = A; B <= n; ++B )
if( F[ i ][ k ][ A ][ B ] != -1 )
Upd( F[ i ][ j ][ min( A, W[ j ] ) ][ max( B, W[ j ] ) ], F[ i ][ k ][ A ][ B ] + G[ k + 1 ][ j - 1 ] );
for( int A = 1; A <= n; ++A )
for( int B = A; B <= n; ++B )
if( F[ i ][ j - 1 ][ A ][ B ] != -1 )
Upd( F[ i ][ j ][ min( A, W[ j ] ) ][ max( B, W[ j ] ) ], F[ i ][ j - 1 ][ A ][ B ] );
for( int k = i; k < j; ++k )
for( int A = 1; A <= n; ++A )
for( int B = A; B <= n; ++B )
if( F[ i ][ k ][ A ][ B ] != -1 )
Upd( G[ i ][ j ], F[ i ][ k ][ A ][ B ] + G[ k + 1 ][ j ] + a + b * ( Ref[ B ] - Ref[ A ] ) * ( Ref[ B ] - Ref[ A ] ) );
for( int A = 1; A <= n; ++A )
for( int B = A; B <= n; ++B )
if( F[ i ][ j ][ A ][ B ] != -1 )
Upd( G[ i ][ j ], F[ i ][ j ][ A ][ B ] + a + b * ( Ref[ B ] - Ref[ A ] ) * ( Ref[ B ] - Ref[ A ] ) );
}
printf( "%d\n", G[ 1 ][ n ] );
return 0;
}