[CF183D]T-shirt

题目大意：

有\(n(n\le3000)\)个人和\(m(m\le300)\)种T恤，每个人都有一种喜欢的T恤，你知道每个人喜欢每种T恤的概率\(p_{i,j}\)。

请你选定\(n\)件体恤的种类，人们会按照编号从\(1\sim n\)挑选T恤，如果剩下还有他喜欢的，则会选走，否则不变。

求送出T恤件数的最大期望。

思路：

用\(f[i][j][k]\)表示对于第\(i\)件T恤，前\(j\)个人中有\(k\)个人喜欢的概率。\(g[i][j]\)表示对于第\(i\)种T恤，选取\(j\)件时对答案贡献的期望值。

\(f\)的转移方程显然，同时也不难得到\(g\)的状态转移方程：

\[g[i][j]=\sum_{k=0}^jk\cdot f[i][n][k]+\sum_{k=j+1}^nj\cdot f[i][n][k]
\]

这样的动态规划是\(\mathcal O(nm^2)\)的。

考虑优化，对\(g\)的相邻两项作差，得到：

\[g[i][j+1]-g[i][j]=1-\sum_{k=0}^j f[i][n][k]
\]

显然这个差值\(\Delta\)表示再加入一条这样的T恤对答案的贡献，而它又是单调递减的，因此每次选取最大的\(\Delta\)更新一定最优。

一开始只计算\(f[i][j][0]\)和\(\Delta[i][0]\)，然后每次选取\(\Delta\)最大的T恤更新答案，然后对相应的T恤进行更新\(f\)和\(\Delta\)即可。这样可以同时省掉\(f\)的第三维。

时间复杂度\(\mathcal O(nm+n^2)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=3001,M=301;

double p[N][M],f[M][N],del[M];

//f[i][j]: 第i种衣服前j个人有cnt[i]个人喜欢的概率

//del[i]: 新加入第i种衣服对答案的贡献

int main() {

	const int n=getint(),m=getint();

	for(register int i=1;i<=n;i++) {

		for(register int j=1;j<=m;j++) {

			p[i][j]=getint()/1000.;

		}

	}

	for(register int i=1;i<=m;i++) {

		f[i][0]=1;

		for(register int j=1;j<=n;j++) {

			f[i][j]=f[i][j-1]*(1-p[j][i]);

		}

		del[i]=1-f[i][n];

	}

	double ans=0;

	for(register int i=0;i<n;i++) {

		const int k=std::max_element(&del[1],&del[m]+1)-del;

		ans+=del[k];

		for(register int i=n;i>=1;i--) {

			f[k][i]=f[k][i-1]*p[i][k];

		}

		f[k][0]=0;

		for(register int i=2;i<=n;i++) {

			f[k][i]+=f[k][i-1]*(1-p[i][k]);

		}

		del[k]-=f[k][n];

	}

	printf("%.12f\n",ans);

	return 0;

}

巴特西

[CF183D]T-shirt

[CF183D]T-shirt

题目大意：

思路：

源代码：

最新文章

热门文章