「THUSC 2016」成绩单

题目链接

题目大意

题面还是比较好理解的。值得注意的是，如果取了中间一段，两边的会连成一段。

解题思路

两维的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;
}