题目描述:
很久很久以前, 一位老人和他的妻子住在蔚蓝的海边. 有一天, 这位老人前去捕鱼, 他捉到了一条活着的金鱼. 鱼说:"噢, 老渔人! 我祈求你放我回到海里, 这样的话我保证给你 n 样礼物 -- 任何你想要的礼物!" 鱼给了老人一张礼物的清单并附上了礼物的价值. 清单上的一些礼物可能会有相同的名称, 不同的价值, 也可能会有不同的名称, 相同的价值. 然而, 清单上不会出现名称和价值都相同的礼物. 老人可以向鱼索要清单上的 n 个礼物. 假设清单上有 p 样礼物价值相同, 则该礼物不能被索要超过 p 次. 老人知道, 如果他索要同一个名称 s 次, 那么金鱼会等概率地随机选择该名称下的 s 样礼物. 老人想要满足他贪心的妻子, 所以他会选择价值最高的 n 样礼物. 此外, 如果有不同的方法选择最高价值的 n 样礼物, 他会等概率地采用其中任意一个方法. 老人想知道, 他能拿到 n 样价值最高的礼物的概率是多少. 然而他不怎么擅长概率论, 于是就来向你求助.
输入格式
第一行有两个整数 n 和 m,n 代表老人想要的礼物数量, m 代表清单上各不相同的名称的数量. 接下来有 m 行, 第 i 行首先包括一个整数 ki(ki> 0), 代表第 i 个名称下礼物的数量. 接着, ki 个各不相同的整数 cij(1<=cij<=109) 是这些礼物的价格.
输出格式
输出仅一行: 一个实数 -- 老人拿到 n 样价值最高的礼物的概率. 绝对误差不超过 10-9 时, 输出被认为是正确的.
样例
- gift1.in gift1.out
- 3 1
- 3 10 20 30
- 1.000000000
- ////////////
- gift2.in gift2.out
- 3 2
- 1 40
- 4 10 20 30 40
- 0.166666667
- /////////////
- gift3.in gif3.out
- 3 2
- 3 1 2 3
- 1 1
- 0.666666667
首先能够发现有一些礼物是必须选的, 设编号为 $i$ 的礼物中必须选的个数为 $cnt[i]$, 有一些可能选的.
然后发现必须选的礼物一定是所有礼物中价值第 $n$ 大的, 记为 $val[n]$, 并且可能选的那些一定等于 $val[n]$, 并记录等于 $val[n]$ 的礼物个数 $ry$, 应该选价值为 $val[n]$ 的礼物个数 $rm$.
题中又说了编号相同则价值不会相同, 所以同一编号下最多只会有一个是可能选的.
可以暴力枚举那些编号是选的, 然后除上组合数. 最后再除以 $C[ry][rm]$.
暴力复杂度指数级别, 显然过不了这题, 于是加上个记忆化.
设 $F[i][j]$ 表示考虑前 $i$ 编号的礼物, 已经选了 $j$ 个可以选的最后成功的概率.
那么有初始值 $F[0][0]=1$, 答案为 $F[m][rm]/C[ry][rm]$.
有转移:$F[i][j]=F[i-1][j]/C[k[i]][cnt[i]]$. 如果 $i$ 编号中有可能选的, 则需要额外加上 $F[i-1][j-1]/C[k[i]][cnt[i]+1]$.
时间复杂度 $O(nm)$
代码:
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- typedef double f3;
- int n,m,k[1050],val[1050],a[1050][1050],cnt[1050],w[1050],is[1050];
- f3 C[1050][1050],f[1030][1030];
- inline bool cmp(int x,int y) {return x>y;}
- int main() {
- //freopen("gift.in","r",stdin);
- //freopen("gift.out","w",stdout);
- scanf("%d%d",&n,&m);
- int i,j;
- int tot=0;
- for(i=1;i<=m;i++) {
- scanf("%d",&k[i]);
- for(j=1;j<=k[i];j++) {
- scanf("%d",&a[i][j]);
- val[++tot]=a[i][j];
- }
- }
- int ry=0,rm=0;
- sort(val+1,val+tot+1,cmp);
- int v=val[n];
- for(i=1;i<=m;i++) {
- for(j=1;j<=k[i];j++) {
- if(a[i][j]>v) cnt[i]++;
- if(a[i][j]==v) {
- w[++ry]=i;
- is[i]=1;
- }
- }
- }
- for(i=n;i>=1;i--) {
- if(val[i]==val[n]) rm++;
- else break;
- }
- for(i=0;i<=tot;i++) C[i][0]=C[i][i]=1;
- for(i=1;i<=tot;i++) {
- for(j=1;j<=i;j++) {
- C[i][j]=C[i-1][j]+C[i-1][j-1];
- }
- }
- f3 tmp=C[ry][rm];
- //printf("%d\n",tot);
- //for(i=0;i<=ry;i++) f[0][i]=1;
- f[0][0]=1;
- for(i=1;i<=m;i++) {
- for(j=0;j<=rm;j++) {
- if(is[i]&&j) {
- f[i][j]=f[i-1][j-1]/C[k[i]][cnt[i]+1];
- }
- f[i][j]+=f[i-1][j]/C[k[i]][cnt[i]];
- //printf("%.9f\n",(double)f[i][j]);
- }
- }
- printf("%.9f\n",f[m][rm]/tmp);
- }
来源: http://www.bubuko.com/infodetail-2594558.html