专栏文章

「题单题解」最优化入门

CCoffee_zzz/xin
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhl1zw
此快照首次捕获于
2025/12/02 02:32
3 个月前
此快照最后确认于
2025/12/02 02:32
3 个月前
查看原文

CF183D T-shirt

题解
考虑 dp。设 Fi,j,kF_{i,j,k} 表示，对于第 ii 种衣服，考虑到第 jj 个人，有恰好 kk 个人的尺寸合适的概率。容易得到转移方程：
Fi,j,k=Fi,j−1,k−1×pj,i+Fi,j−1,k×(1−pj,i)F_{i,j,k}=F_{i,j-1,k-1} \times p_{j,i} + F_{i,j-1,k} \times (1-p_{j,i})
设 Ei,jE_{i,j} 表示选择 jj 件第 ii 种衣服的期望收益，则有：
Ei,j=∑k=0jFi,n,k×k+∑k=j+1nFi,n,k×jE_{i,j}=\sum_{k=0}^j F_{i,n,k} \times k+\sum_{k=j+1}^n F_{i,n,k} \times j
再设 Gi,jG_{i,j} 表示，考虑到第 ii 件衣服，且目前一共选择了 jj 件的期望收益。由于每种衣服之间是独立的，可以得到转移方程为：
Gi,j=∑k=0jGi−1,k+Ei,j−k。G_{i,j}=\sum_{k=0}^j G_{i-1,k}+E_{i,j-k}。
总时间复杂度为 O(n2m)\mathcal O(n^2m)，考虑优化。
注意到：
Ei,j−Ei,j−1=∑k=jnFi,n,kE_{i,j}-E_{i,j-1}=\sum_{k=j}^n F_{i,n,k}
而 Fi,n,k≥0F_{i,n,k} \ge 0，所以 EiE_i 的差分数组 ΔEi\Delta E_i 是单调不增的，于是可以考虑不断地贪心购买贡献最大的衣服。
具体地，设 cic_i 表示当前购买的第 ii 种衣服的数量，DiD_i 表示当前再买一件第 ii 种衣服所能带来的贡献，Vi,jV_{i,j} 等于当前的 Fi,j,ciF_{i,j,c_i}，SiS_i 等于当前的 ∑k=0ciFi,n,k\sum\limits_{k=0}^{c_i} F_{i,n,k}。由于 ∑k=0nFi,n,k=1\sum\limits_{k=0}^n F_{i,n,k}=1，所以有：
Di=Ei,ci+1−Ei,ci=∑k=ci+1nFi,n,k=1−∑k=0ciFi,n,k=1−Si\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}
于是，每次选择 DiD_i 最大的 ii，并更新所有数组中变化的元素即可。
时间复杂度 O(n2+nm)\mathcal O(n^2+nm)。
代码C
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

题解
我们称「支付 cic_i 个碎片直接购买第 ii 个遗物」为固定操作，「支付 xx 个碎片随机获得 nn 个遗物中的一个」为随机操作，cic_i 为第 ii 个遗物的价值。记所有遗物的价值之和为 ss。
首先有一个显然的性质是，因为 x≤cix \le c_i，所以一定是先进行随机操作再进行固定操作，也就是说在进行固定操作后一定不会再进行随机操作。
设目前已经拥有 ii 个遗物，那么通过一次随机操作获得一个新遗物的概率为 n−in\dfrac {n-i} n，也就是说期望 nn−i\dfrac n{n-i} 次随机操作获得一个新遗物。于是可以得到，通过随机操作获得一个新遗物的期望花费为 (nn−i+1)×x2\left(\dfrac n {n-i}+1\right) \times \dfrac x 2。
接下来考虑求出通过固定操作获得一个新遗物的期望花费，这样我们才能决定下一步要用固定操作还是随机操作。
这里有一个巧妙的转化是，因为固定操作需要我们决定对哪个遗物进行操作，处理起来比较麻烦，所以我们可以考虑把固定操作转化为随机操作的形式。具体地，设目前已经拥有 ii 个遗物，所有拥有的遗物的价值之和为 pp，那么所有未拥有的遗物的价值之和为 s−ps-p；由于进行固定操作后一定只会一直进行固定操作，所以我们可以当作每次固定操作会在剩下的 n−i\boldsymbol{n-i} 个遗物中以 s−pn−i\boldsymbol{\dfrac {s-p}{n-i}} 的花费随机获得一个遗物，也就是说通过固定操作获得一个新遗物的期望花费为 s−pn−i\dfrac {s-p}{n-i}。
将两种操作结合起来可以得到，设目前已经拥有 ii 个遗物，所有拥有的遗物的价值之和为 pp，那么随机获得一个新遗物的期望花费为 min⁡((nn−i+1)×x2,s−pn−i)\min\left(\left(\dfrac n {n-i}+1\right) \times \dfrac x 2,\dfrac {s-p}{n-i}\right)，并且我们不需要做任何决策，只需要一直随机就好。
那么现在，我们只需要求出，对于每一对 (i,p)(i,p)，其出现的概率为多少。设 dpi,pdp_{i,p} 表示当前选择了 ii 个遗物，且被选择的遗物的价值之和为 pp 的方案数。由于每个大小为 ii 的子集被选中的概率相等，所以将 dpi,pdp_{i,p} 除以 (ni)n\choose i 即可得到 (i,p)(i,p) 出现的概率 fi,pf_{i,p}，其中 dpi,pdp_{i,p} 可以直接背包求出。
最后，对于每个 i∈[0,n)i\in[0,n) 和 p∈[0,sum)p \in [0,sum)，计算 fi,p×min⁡((nn−i+1)×x2,s−pn−i)f_{i,p} \times \min\left(\left(\dfrac n {n-i}+1\right) \times \dfrac x 2,\dfrac {s-p}{n-i}\right) 之和即可。
时间复杂度 O(n2s)\mathcal O(n^2s)，瓶颈在于背包。
代码CPP
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);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...