之前牛客网发过一次题解，感觉在acwing发更合适一点

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

int a[ 1000010 ];
int n;

int main()
{
    cin >> n;
    vector< int > left;
    vector< int > right;
    for( int i = 1; i <= n; i ++ ) cin >> a[ i ];
    int deep = 0;
    int sum = 0;
    int t = 1;
    while( true )
    {
        if( sum + t > n ) break;
        deep ++;
        sum += t;
        if( deep == 1 )
        {
            left.push_back( a[ sum ] );
           // cout << "deep " << deep + " " << a[ sum ] << endl;
        }
        else
        {
            left.push_back( a[ sum - t + 1 ] );
            right.push_back( a[ sum ] );
           // cout << "deep " << deep << " " << a[ sum - t + 1 ] << " " << a[ sum ] << endl;
        }
        t *= 2;
    }
    int tot = 0;
    int cnt = 0;
    t = 1;
    while( cnt <= deep )
    {
        tot += t;
        t *= 2;
        cnt ++;
    }
    t /= 2;
    int res =  t - ( tot - n );
    //cout << res << endl;
    for( int i = n - res + 1; i <= n; i ++ ) left.push_back( a[ i ] );
    int top = ( res + 1 ) / 2;
    int topres = t / 2 - top;
    int now = n - res;
    for( int i = now - topres + 1; i < now; i ++ ) left.push_back( a[ i ] );
    reverse( right.begin(), right.end() );
    for( auto x: right )
    {
        left.push_back( x );
    }
    int sz = left.size();
    for( int i = 0; i < sz - 1; i ++ ) cout << left[ i ] << " ";
    cout << left[ sz - 1 ] << endl;
    return 0;
}

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

#define  ll long long

int n, m;
ll v[ 205 ][ 2005 ];
ll sum[ 2050 ][ 205 ];
ll pre[ 2050 ];

int hh, tt;
ll q[ 2050 ], dp[ 2050 ];

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= m; j ++ )
    {
        cin >> v[ i ][ j ];
        v[ i ][ j + m ] = v[ i ][ j ];
    }
    for( int i = 1; i <= m * 2; i ++ )
    {
        for( int j = 1; j <= n; j ++ )
        {
            sum[ i ][ j ] = sum[ i ][ j - 1 ] + v[ j ][ i ];
        }
    }
    ll goal = LONG_LONG_MIN;
    for( int i = 1; i <= n; i ++ )
    for( int j = i; j <= n; j ++ )
    {
        for( int k = 1; k <= m * 2; k ++ ) pre[ k ] = pre[ k - 1 ] + sum[ k ][ j ] - sum[ k ][ i - 1 ];
        ll ans = LONG_LONG_MIN;
        hh = 0;
        tt = -1;
        dp[ 0 ] = 0;
        q[ ++ tt ] = 0;
        for( int k = 1; k <= m * 2; k ++ )
        {
            if( hh <= tt && k - q[ hh ] > m ) hh ++;
            if( hh <= tt ) dp[ k ] = pre[ k ] - pre[ q[ hh ] ];
            while( hh <= tt && pre[ q[ tt ] ] >= pre[ k ] ) tt --;
            q[ ++ tt ] = k;
        }
        for( int k = 1; k <= m * 2; k ++ ) goal = max( goal, dp[ k ] );
    }
    cout << goal << endl;
    return 0;
}

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

int dp[ 305 ][ 305 ][ 21 ];
int n, k;

int main()
{
    cin >> n >> k;
    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= n; j ++ )
    for( int x = 0; x <= k; x ++ ) dp[ i ][ j ][ x ] = 100000000;

    for( int q = 0; q <= k; q ++ )
    for( int len = 1; len  <= n; len ++ )
    {
        for( int i = 1; i + len - 1 <= n; i ++ )
        {
            int j = i + len - 1;
            if( i == j )
            {
                dp[ i ][ j ][ q ] = 0;
            } else {
                if( q != 0 )
                {
                    dp[ i ][ j ][ q ] = min(dp[ i + 1 ][ j ][ q - 1 ], dp[ i ][ j - 1 ][ q - 1 ]);
                    for( int x = i + 1; x < j; x ++ )
                    {
                        dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], max( dp[ i ][ x - 1 ][ q - 1 ], dp[ x + 1 ][ j ][ q - 1 ] ) );
                    }
                }
                dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], i + dp[ i + 1 ][ j ][ q ] );
                dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], j + dp[ i ][ j - 1 ][ q ] );
                for( int x = i + 1; x < j; x ++ )
                {
                    dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], x + max( dp[ i ][ x - 1 ][ q ], dp[ x + 1 ][ j ][ q ] ) );
                }
            }
        }
    }
    cout << dp[ 1 ][ n ][ k ] << endl;
}