「题单题解」最优化入门

· · 算法·理论

CF183D T-shirt

:::info[题解]

考虑 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)。

:::

:::success[代码]

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);
}

:::

CF1267G Game Relics

:::info[题解]

我们称「支付 c_i 个碎片直接购买第 i 个遗物」为固定操作，「支付 x 个碎片随机获得 n 个遗物中的一个」为随机操作，c_i 为第 i 个遗物的价值。记所有遗物的价值之和为 s。

首先有一个显然的性质是，因为 x \le c_i，所以一定是先进行随机操作再进行固定操作，也就是说在进行固定操作后一定不会再进行随机操作。

设目前已经拥有 i 个遗物，那么通过一次随机操作获得一个新遗物的概率为 \dfrac {n-i} n，也就是说期望 \dfrac n{n-i} 次随机操作获得一个新遗物。于是可以得到，通过随机操作获得一个新遗物的期望花费为 \left(\dfrac n {n-i}+1\right) \times \dfrac x 2。

接下来考虑求出通过固定操作获得一个新遗物的期望花费，这样我们才能决定下一步要用固定操作还是随机操作。

这里有一个巧妙的转化是，因为固定操作需要我们决定对哪个遗物进行操作，处理起来比较麻烦，所以我们可以考虑把固定操作转化为随机操作的形式。具体地，设目前已经拥有 i 个遗物，所有拥有的遗物的价值之和为 p，那么所有未拥有的遗物的价值之和为 s-p；由于进行固定操作后一定只会一直进行固定操作，所以我们可以当作每次固定操作会在剩下的 \boldsymbol{n-i} 个遗物中以 \boldsymbol{\dfrac {s-p}{n-i}} 的花费随机获得一个遗物，也就是说通过固定操作获得一个新遗物的期望花费为 \dfrac {s-p}{n-i}。

将两种操作结合起来可以得到，设目前已经拥有 i 个遗物，所有拥有的遗物的价值之和为 p，那么随机获得一个新遗物的期望花费为 \min\left(\left(\dfrac n {n-i}+1\right) \times \dfrac x 2,\dfrac {s-p}{n-i}\right)，并且我们不需要做任何决策，只需要一直随机就好。

那么现在，我们只需要求出，对于每一对 (i,p)，其出现的概率为多少。设 dp_{i,p} 表示当前选择了 i 个遗物，且被选择的遗物的价值之和为 p 的方案数。由于每个大小为 i 的子集被选中的概率相等，所以将 dp_{i,p} 除以 n\choose i 即可得到 (i,p) 出现的概率 f_{i,p}，其中 dp_{i,p} 可以直接背包求出。

最后，对于每个 i\in[0,n) 和 p \in [0,sum)，计算 f_{i,p} \times \min\left(\left(\dfrac n {n-i}+1\right) \times \dfrac x 2,\dfrac {s-p}{n-i}\right) 之和即可。

时间复杂度 \mathcal O(n^2s)，瓶颈在于背包。

:::

:::success[代码]

const int N=105,V=10005;
int n,x,c[N],s;
double fac[N],dp[N][V],p[N],ans;
void solve(){
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>c[i],s+=c[i];
    fac[0]=1,dp[0][0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
    for(int i=1;i<=n;i++) for(int j=i;j>=1;j--) for(int k=c[i];k<=s;k++) dp[j][k]+=dp[j-1][k-c[i]];
    for(int i=0;i<n;i++) p[i]=(1.0*n/(n-i)+1)*x/2;
    for(int i=0;i<n;i++) for(int k=0;k<s;k++) ans+=dp[i][k]/fac[n]*fac[n-i]*fac[i]*min(p[i],1.0*(s-k)/(n-i));
    printf("%.10lf\n",ans);
}

:::