SRM486 Div1 Medium(450) QuickSort - kusano

Lの値を1〜len(L)の連続した値に置き換えて考えると、quick-sort(L)に渡されるLは常に連続した値である。そのようなLはn(n-1)/2通りしかない。

#include <vector>
#include <algorithm>
using namespace std;

const int N = 50;
static double memo[N+1][N+1];

double cost( vector<int> L )
{
    int n = (int)L.size();

    if ( n < 2 )
        return 0;

    double &m = memo[*min_element(L.begin(),L.end())]
                    [*max_element(L.begin(),L.end())];
    if ( m >= 0 )
        return m;

    double c = 0;

    for ( int i=0; i<n; i++ )
    {
        vector<int> L0;
        vector<int> L1;

        for ( int j=0; j<n; j++ )
        {
            if ( L[j]<L[i] )  L0.push_back( L[j] );
            if ( L[j]>L[i] )  L1.push_back( L[j] );
            if ( L[j]<L[i] && j>i )  c += 1;
            if ( L[j]>L[i] && j<i )  c += 1;
        }

        c += cost(L0) + cost(L1);
    }
    
    return m = c / n;
}

class QuickSort{public:
double getEval( vector <int> L )
{
    for ( int i=1; i<=N; i++ )
    for ( int j=1; j<=N; j++ )
        memo[i][j] = -1;

    return cost(L);
}};