SRM 486 div1 med: QuickSort

問題

TopCoder Statistics - Problem Statement

解法

配列の最小値と最大値を決めると, 配列内の数字の並びは一定になります。
よって, dp[mini][maxi] = (配列内の最小値が mini で, 最大値が maxi であるような配列で, swap する回数の期待値) とすれば, 普通に dp 出来ます。

vector<int> L;
double dp[55][55];

double dfs(int mini, int maxi) {
    double& ret = dp[mini][maxi];
    if (ret >= 0) return ret;
    ret = 0;
    if (mini == maxi) return ret;
    vector<int> v;
    for (int el : L) {
        if (mini <= el && el <= maxi) v.push_back(el);
    }
    vector<int> w = v;
    sort(w.begin(), w.end());
    int n = v.size();
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (j < i && v[j] > v[i]) cnt++;
            if (j > i && v[j] < v[i]) cnt++;
        }
        double tmp = cnt;
        int index = lower_bound(w.begin(), w.end(), v[i]) - w.begin();
        if (index > 0) tmp += dfs(mini, w[index-1]);
        if (index < n-1) tmp += dfs(w[index+1], maxi);
        ret += tmp/n;
    }
    return ret;
}

class QuickSort {
public:
    double getEval(vector <int> L) {
        ::L = L;
        for (int i = 0; i < 55; i++) for (int j = 0; j < 55; j++) dp[i][j] = -1;
        int mini = 55, maxi = 0;
        for (int el : L) {
            mini = min(mini, el);
            maxi = max(maxi, el);
        }
        return dfs(mini, maxi);
    }
};