题解：CF183D T-shirt

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

首先考虑一个暴力 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))

。

CPP

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

题解：CF183D T-shirt

文章操作

相关推荐

评论

题解：CF183D T-shirt