题目传送门
题目大意
餐厅有$n$张桌子，第$i$张桌子可以容纳$c_i$个人，有$t$组客人，每组客人的人数等概率是$[1, g]$中的整数。
每来一组人数为$x$客人，餐厅如果能找到最小的$c_j$使得$c_j \geqslant x$，那么就会把这张桌子分配给这些客人，并得到$x$的收益。
问期望的收益。
好像可以枚举每一种人数，然后算一下，但时间复杂度很爆炸。
先添加若干个容量为$\infty$的桌子。这样每组人一定能够分配到一张桌子，只是可能没有收益。
考虑最后答案一定是将桌子排序后，若干段连续的桌子被占用。
用$f_{l, r}$表示恰好$[l, r]$这段桌子被占用的所有方案的收益总和和方案数。每次转移考虑枚举最后一组人来的时候占用的桌子，假如它是$mid$，那么最后一组人可行的人数是$(c_{l - 1}, c_{mid}]$。
然后做一个背包，$h_{i, j}$表示考虑到在时刻$i$及其之后来的人，被占用的最靠左的左端点是$j$，所有方案的收益总和和方案数。转移的时候枚举这一段的长度，以及前一段的区间的左端点，注意两个区间不能相交。后者用一个后缀和优化掉。
注意每组人是带标号的，所以合并两个方案的时候还需要分配标号。
Code
/**
* Codeforces
* Gym#101623E
* Accepted
* Time: 46ms
* Memory: 2600k
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
typedef bool boolean; typedef long double ld;
typedef pair<ld, ld> pdd; pdd operator + (const pdd& a, const pdd& b) {
return pdd(a.first + b.first, a.second + b.second);
} pdd operator * (const pdd& a, const pdd& b) {
return pdd(a.first * b.second + a.second * b.first, a.second * b.second);
} pdd operator * (const pdd& a, ld x) {
return pdd(a.first * x, a.second * x);
} ld nature_sum(int x) {
return x * (x + ) >> ;
} const int N = ; int n, g, t;
vector<int> c;
ld C[N << ][N << ];
pdd f[N << ][N << ], h[N][N << ], s[N][N << ]; inline void init() {
scanf("%d%d%d", &n, &g, &t);
c.resize(n);
for (int i = ; i < n; i++) {
scanf("%d", &c[i]);
c[i] = min(c[i], g);
}
for (int i = ; i < t; i++)
c.push_back(g + );
sort(c.begin(), c.end());
n = c.size();
} inline void solve() {
C[][] = ;
for (int i = ; i <= n; i++) {
C[i][] = C[i][i] = ;
for (int j = ; j < i; j++)
C[i][j] = C[i - ][j] + C[i - ][j - ];
} for (int r = ; r < n; r++)
for (int l = r; ~l; l--) {
for (int mid = l; mid <= r; mid++) {
pdd val; //(0, 1);//C[r - l][r - mid]);
if (c[mid] > g)
val = pdd(, g - ((l) ? (min(c[l - ], g)) : ()));
else
val = pdd(nature_sum(c[mid]) - ((l) ? (nature_sum(c[l - ])) : ()), c[mid] - ((l) ? (c[l - ]) : ()));
pdd vall = (mid > l) ? (f[l][mid - ] * C[r - l][r - mid]) : (pdd(, ));
pdd valr = (mid < r) ? (f[mid + ][r]) : (pdd(, ));
f[l][r] = f[l][r] + (vall * val * valr);
}
// cerr << l << " " << r << " " << f[l][r].first << " " << f[l][r].second << '\n';
} for (int i = ; i < t; i++)
for (int j = ; j < n - t + i + ; j++)
h[i][j] = f[j][j + t - i - ];
for (int i = t; i--; ) {
int all = t - i;
for (int j = ; j + all < n; j++) {
for (int k = i + ; k < t; k++) {
int put = k - i;
// cerr << i << " " << j << " " << k << " " << all << " " << put << '\n';
ld comb = C[all][put];
h[i][j] = h[i][j] + (f[j][j + put - ] * comb * s[k][j + put + ]);
}
// cerr << i << " " << j << " " << h[i][j].first << " " << h[i][j].second << '\n';
}
s[i][n - ] = h[i][n - ];
for (int j = n - ; j >= ; j--)
s[i][j] = s[i][j + ] + h[i][j];
}
pdd ans(, );
for (int i = ; i < n; i++)
ans = ans + h[][i];
// cout << (ans.first / ans.second) << '\n';
double E = ans.first / ans.second;
printf("%.9lf", E);
} int main() {
init();
solve();
return ;
}