题目描述
$n\le 3000,m\le 300$
思路
肯定是要算贡献的。
考察一个礼物的贡献，用 $g_{i,j}$ 表示其贡献，即：第 $i$ 种礼物有 $j$ 个，期望被拿走的个数。
考虑从 $g_{i,j}$ 转移到 $g_{i,j+1}$，发现这取决于喜欢这种礼物的人数。考虑有 $k$ 个人喜欢这种礼物的概率，用 $h_{i,j,k}$ 表示前 $j$ 个人中有 $k$ 个人喜欢 $i$ 礼物的概率。此时 $g_{i,j}=\sum_{x=0}^{n}\min (x,j)h_{i,n,x}$，进而 $g_{i,j}-g_{i,j-1}=\sum_{x=j}^nh_{i,n,x}$。
进而买 $j$ 件前 $i$ 种礼物的期望值为：$f_{i,j}=\max(f_{i-1,j-x}+g_{i,x})$。发现 $g$ 的差分不增，故可以转换为贪心，每次寻找 $g$ 增量最大的种类。
此时瓶颈在于求 $h$。
$$
h_{i,j,k}=(1-p)h_{i,j-1,k}+ph_{i,j-1,k-1}
$$
发现我们每次用一个 $\Delta g$ 更新后，只需知道 $\sum_{x=j}^nh_{i,n,x}$，而之前一定已经求过 $\sum_{x=j-1}^nh_{i,n,x}$，故只需求 $h_{i,n,j-1}$，而此前必求过 $h_{i,n,j-2}$，故可以递推，并不需要知道全部 $h$。
复杂度是对的。
Code
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
| #include<bits/stdc++.h>
using namespace std;
int n,m,cnt[301];
double p[3001][301],g[301],h[301][3001][2],ans;
void upd(int x,int y)
{
for(int i=1;i<y;i++)h[x][i][y&1]=0;
for(int i=max(y,1);i<=n;i++)
h[x][i][y&1]=h[x][i-1][(y&1)^1]*p[i][x]+h[x][i-1][y&1]*(1.0-p[i][x]);
}
int main()
{
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
int _;scanf("%d",&_);p[i][j]=0.001*_;
}
for(int i=1;i<=m;i++)h[i][0][0]=1.0;
for(int i=1;i<=m;i++)upd(i,0);
for(int i=1;i<=m;i++)g[i]=1-h[i][n][0];
for(int i=1;i<=n;i++)
{
int _=1;
for(int j=2;j<=m;j++)if(g[j]>g[_])_=j;
ans+=g[_];
upd(_,++cnt[_]);g[_]-=h[_][n][cnt[_]&1];
}
printf("%.10lf\n",ans);
return 0;
}
|
Summary
发现问题的性质。