题意

给一段程序：

int qsort(int L, int R) {
	if (L >= R) return 0;
	int i = L, j = R;
	int x = Random.Next();
	int x0 = A[x];
	assert(L <= x && x <= R);
	while (i < j) {
		while (A[i] < A[x]) i++;
		while (A[j] > A[x]) j--;
		if (i <= j) {
			if (i == x) x = j;
			else if (j == x) x = i;
			swap (A[i], A[j]);
			i++; j--;
		}
	}
	swap(A[x], A[x0]);
	return R - L + qsort(L, x0 - 1) + qsort (x0 + 1, R);
}

其中，在最后一行先运行 qsort(L, x0 - 1) 再运行 qsort (x0 + 1, R)。由于随机数不取模，x 可能越界，排序会被 assert(L <= x && x <= R); 终止，此时排序结束且没有返回值。

给定长度 $N$ 和可能用到的前 $N$ 个随机数。对于所有的长度为 $N$ 的排列，求 qsort(1,N) 可能的最大值是多少，并输出其中一个最大的排列。

$n\leq 50,1\leq\text{Random}_i\leq N$ 。

口胡

看到这种题慌了。但其实不要慌。

多分析多模拟。快排就是随机选个数，把比它小的放左边，大的放右边。

有点像记忆化搜索，然后对于 $L,R$ 状态用 DP 存储，进而想到区间 DP，但是只有 $L,R$ 维护不了随机数，那就加状态，设 $f_{L,R,k,l}$ 表示处理 $[L,R]$ 时，使用了 $k$ 个随机数，下标从 $l$ 开始。转移时枚举排序后位置、左边部分需要的随机数个数。

还原排列就考虑选取排序前后数的位置手玩可以得到。