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

文章操作

相关推荐

评论

CF183D T-shirt 题解