• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CF183D-T-shirtx【dp,贪心】

admin

11月 28, 2021

正题

题目链接:https://www.luogu.com.cn/problem/CF183D


题目大意

(n)个人,(m)种衣服,给出每个人喜欢某件衣服的概率,你可以选择(n)件衣服带过去(可以重复款式)。求最大化能拿到喜欢衣服人的期望数量。

(1leq nleq 3000,1leq mleq 300)


解题思路

考虑暴力的(dp),设(f_{i,j,k})表示对于前(k)个人种类为(j)的衣服选择了(i)件。

这样显然过不了。

但是考虑答案,假设我们第(i)种衣服选择了(k)件那么产生的贡献就是

[sum_{j=0}^k i imes f_{i,j,n}+ksum_{j=k+1}^nf_{i,j,n}
]

然后对于(k->k+1)会多产生的贡献就是(1-sum_{j=1}^kf_{i,j,n})。考虑到这个值肯定是单调递减的,所以贡献函数是一个关于(k)的上凸函数。

然后就是很经典的方法了,每次暴力选择一个能扩展的最大的扩展即可。

时间复杂度(O(n(n+m)))


code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=310,N=3100;
int n,m,k[M];double s[M],f[2][M][N],a[M][N],ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)f[0][i][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf("%lf",&a[j][i]);
			a[j][i]/=1000.0;
			f[0][j][i]=f[0][j][i-1]*(1-a[j][i]);
		}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)
			f[1][i][j]=f[1][i][j-1]*(1-a[i][j])+f[0][i][j-1]*a[i][j];
		k[i]=1;s[i]=f[0][i][n];
	}
	for(int p=1;p<=n;p++){
		int pos=1;
		for(int i=2;i<=m;i++)
			if(s[i]<s[pos])pos=i;
		ans=ans+(1-s[pos]);
		s[pos]=s[pos]+f[k[pos]][pos][n];
		k[pos]^=1;int o=k[pos];
		for(int i=0;i<=n;i++)f[o][pos][i]=0;
		for(int i=1;i<=n;i++)
			f[o][pos][i]=f[o][pos][i-1]*(1-a[pos][i])+f[!o][pos][i-1]*a[pos][i];
	}
	printf("%.12lf
",ans);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。