CF183D T-shirt 题解

· · 题解

考虑 dp。设 F_{i,j,k} 表示，对于第 i 种衣服，考虑到第 j 个人，有恰好 k 个人的尺寸合适的概率。容易得到转移方程：

F_{i,j,k}=F_{i,j-1,k-1} \times p_{j,i} + F_{i,j-1,k} \times (1-p_{j,i})

设 E_{i,j} 表示选择 j 件第 i 种衣服的期望收益，则有：

E_{i,j}=\sum_{k=0}^j F_{i,n,k} \times k+\sum_{k=j+1}^n F_{i,n,k} \times j

再设 G_{i,j} 表示，考虑到第 i 件衣服，且目前一共选择了 j 件的期望收益。由于每种衣服之间是独立的，可以得到转移方程为：

G_{i,j}=\sum_{k=0}^j G_{i-1,k}+E_{i,j-k}。

总时间复杂度为 \mathcal O(n^2m)，考虑优化。

注意到：

E_{i,j}-E_{i,j-1}=\sum_{k=j}^n F_{i,n,k}

而 F_{i,n,k} \ge 0，所以 E_i 的差分数组 \Delta E_i 是单调不增的，于是可以考虑不断地贪心购买贡献最大的衣服。

具体地，设 c_i 表示当前购买的第 i 种衣服的数量，D_i 表示当前再买一件第 i 种衣服所能带来的贡献，V_{i,j} 等于当前的 F_{i,j,c_i}，S_i 等于当前的 \sum\limits_{k=0}^{c_i} F_{i,n,k}。由于 \sum\limits_{k=0}^n F_{i,n,k}=1，所以有：

\begin{aligned} D_i&=E_{i,c_i+1}-E_{i,c_i}\\ &=\sum_{k=c_i+1}^n F_{i,n,k}\\ &=1-\sum_{k=0}^{c_i} F_{i,n,k}\\ &=1-S_i \end{aligned}

于是，每次选择 D_i 最大的 i，并更新所有数组中变化的元素即可。

时间复杂度 \mathcal O(n^2+nm)。

const int N=3005,M=305;
int n,m,c[M];
double p[N][M],D[M],W[N],V[M][N],S[M],ans;
void solve(){
    cin>>n>>m;
    for(int i=1,x;i<=n;i++) for(int j=1;j<=m;j++) cin>>x,p[i][j]=x*0.001;
    for(int i=1;i<=m;i++){
        V[i][0]=1;
        for(int j=1;j<=n;j++) V[i][j]=V[i][j-1]*(1-p[j][i]);
        S[i]=V[i][n],D[i]=1-S[i];
    }
    for(int x=1;x<=n;x++){
        int u=1;
        for(int i=1;i<=m;i++) if(D[i]>D[u]) u=i;
        ans+=D[u];
        for(int j=0;j<=n;j++) W[j]=V[u][j];
        V[u][0]=0;
        for(int j=1;j<=n;j++) V[u][j]=W[j-1]*p[j][u]+V[u][j-1]*(1-p[j][u]);
        S[u]+=V[u][n],D[u]=1-S[u],c[u]++;
    }
    printf("%.12lf",ans);
}