Codeforces

Luogu

分析

考虑对于每一件 T-shirt 计算其贡献。下面设当前考虑的 T-shirt 为 $k$。

设 $f_{i, j}$ 表示前 $i$ 个人，有 $j$ 人适合大小为 $k$ 的 T-shirt 的概率，转移为
$$
f_{i, j} = f_{i - 1, j - 1} \times p_{i, k} + f_{i - 1, j} \times (1 - p_{i, k})
$$
设 $g_i$ 表示准备了 $i$ 件大小为 $k$ 的 T-shirt 的，期望有多少人适合，有
$$
g_i = \sum_{j = 0}^i j \times f_{n, j} + \sum_{j = i + 1}^n i \times f_{n, j}
$$
然后分组背包即可，复杂度 $\mathcal{O}(n^2m)$。

可以发现 $g_i$ 是凸的，这是因为
$$
g_{i + 1} - g_i = \sum_{j = i + 1}^n f_{n, j} = 1 - \sum_{j = 0}^i f_{n, j}
$$
是单减的。

因此我们可以每次贪心地找一个 $\Delta g$ 最大的 T-shirt 大小出来。

实现时，我们先求出对每个 T-shirt 大小求出 $f_{n, 0}$ 和 $g_1 - g_0$。在选了一个大小之后，我们求出 $f_{n, c+1}$，然后更新 $g_{c + 1} - g_c$ 即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 3000 + 10, M = 300 + 10;

int n, m;
double p[N][M];
double f[M][N], d[M], g[N];

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            p[i][j] = read() / 1000.0;
    for (int i = 1; i <= m; ++i) {
        f[i][0] = 1;
        for (int j = 1; j <= n; ++j)
            f[i][j] = f[i][j - 1] * (1 - p[j][i]);
        d[i] = 1 - f[i][n];
    }
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
        int k = std::max_element(d + 1, d + m + 1) - d;
        if (d[k] <= 0) break;
        ans += d[k];
        memcpy(g, f[k], sizeof(g));
        f[k][0] = 0;
        for (int j = 1; j <= n; ++j)
            f[k][j] = g[j - 1] * p[j][k] + f[k][j - 1] * (1 - p[j][k]);
        d[k] -= f[k][n];
    }
    printf("%.10lf\n", ans);
    return 0;
}