Fork me on GitHub

Codeforces183D

Codeforces183D题解

题意:

  • 有$n$个人和$m$种T-shirt,每个人都有一种喜欢的T-shirt,然而你只知道他们每个人喜欢某种的概率。
  • 你需要在开始时选定$n$件T-shirt的种类,人们会按照编号从$1$~$n$挑选T-shirt,如果剩下还有他喜欢的,则会选走,否则不变。
  • 请输出最大的期望送出的T-shirt件数。
  • $n \leq 3000,m \leq 300$

题解:

  • 首先我们可以发现每种T-shirt是独立的,只在最后的合并中互相影响。
  • 假设对于第$k$种T-shirt,设$f[i][j]$表示前$i$个人有$j$个人喜欢它的概率。
  • 然后$g[i]$表示在方案中选取了$i$件第$k$种T-shirt的期望。可以发现:
  • 如果这样子暴力算$f$和$g$并合并答案,复杂度是$O(n^2m)$的。
  • 考虑优化。
  • 这个差值显然是单调的,这说明$g$是上凸函数。
  • 所以我们可以跑$n$次循环,记录下来每种T-shirt的$f[1,2,\cdots,n][j]$和$\Delta=g[j+1]-g[j]$,其中$j$代表这种T-shirt已经选的件数,每次选择$\Delta$最大的$i$(编号)进行更新$f$和$\Delta$。
  • 这样复杂度是$O(nm+n^2)$的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define N 3009
#define M 309
using namespace std;
int n,m;
long double p[N][M],delta[M],f[M][N],Ans=0.0,last_f[N],number[M];
void work(int now)
{
number[now]++;
if (number[now]>=n)
{
delta[now]=0.0;
return;
}
for (int i=0;i<=n;i++) last_f[i]=f[now][i];
f[now][0]=0.0;
for (int i=1;i<=n;i++)
f[now][i]=f[now][i-1]*(1.0-p[i][now])+last_f[i-1]*p[i][now];
delta[now]-=f[now][n];
}
int 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;j<=m;j++)
{
int x;
cin>>x;
p[i][j]=(long double)x/1000.0;
}
for (int i=1;i<=m;i++)
{
f[i][0]=1.0;
for (int j=1;j<=n;j++)
f[i][j]=f[i][j-1]*(1.0-p[j][i]);
delta[i]=1.0-f[i][n];
}
for (int i=1;i<=n;i++)
{
long double Max=0.0;
int k=0;
for (int j=1;j<=m;j++)
if (delta[j]>Max)
{
Max=delta[j];
k=j;
}
Ans+=Max;
if (!k) break;
work(k);
}
cout<<fixed<<setprecision(10)<<Ans<<endl;
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces183D

文章作者:wzf2000

发布时间:2017年12月23日 - 22:12

最后更新:2017年12月25日 - 12:12

原始链接:https://wzf2000.github.io/2017/12/23/Codeforces183D/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。