题解：CF183D T-shirt

· · 题解

UPD 2025.4.22：修了一个唐爆了的锅。

Prob. link

首先考虑一个暴力 dp：

令 f_{i,j,k} 表示前 j 个选了 k 个颜色为 i 的，显然有转移 f_{i,j,k}=f_{i,j-1,k}(1-p_{j,i})+f_{i,j-1,k-1}p_{j,i}。

令 g_{i,j} 表示带了 j 件颜色为 i 的衣服的期望人数，容易想到 g_{i,j}=\sum\limits_{k=0}^{j} kf_{i,n,k}+i\sum\limits_{k=j+1}^n f_{i,n,k}。

时间复杂度 O(n^2m)。

考察 g 的变化量：

g_{i,j+1}-g_{i,j}=\sum\limits_{k=j+1}^n f_{i,n,k}=1-\sum\limits_{k=0}^j f_{i,n,k}

容易想到 \Delta g 是单调不增的。

根据期望的线性性，我们把它拆成每件衣服的贡献和后，贪心地取最大的 \Delta g 一定是最优的，因为它一定不会因为取的数目的增加而导致有其它的贡献比它更大。

容易想到这样以后显然可以增加在一个颜色取的数量之后计算 f_{i,\_,j+1} 然后更新 \Delta g，这样单次更新是 O(n) 的，一共取 n 次，所以时间复杂度是 O(n^2) 的。

总时间复杂度 O(n(n+m))。

#include<bits/stdc++.h>
#define int long long
#define double long double
#define endl '\n'
using namespace std;
const int N=3005,M=305;
int n,m;
double p[3005][305],f[2][M][N],delta[M],ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i) for(int j=1,P;j<=m;++j) cin>>P,p[i][j]=P/1000.0;
    for(int i=1;i<=m;++i){
        f[0][i][0]=1;
        for(int j=1;j<=n;++j) f[0][i][j]=f[0][i][j-1]*(1-p[j][i]);
        delta[i]=1-f[0][i][n];
    }
    for(int i=1;i<=n;++i){
        int pos=1;
        for(int j=1;j<=m;++j) if(delta[j]>delta[pos]) pos=j;
        ans+=delta[pos];
        for(int j=1;j<=n;++j) f[1][pos][j]=f[1][pos][j-1]*(1-p[j][pos])+f[0][pos][j-1]*(p[j][pos]);
        delta[pos]-=f[1][pos][n];
        memcpy(f[0][pos],f[1][pos],sizeof(f[0][pos]));
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}