博客

已满分过

题目描述

小林在玩一个抽卡游戏，其中有 n 种不同的卡牌，编号为 1 到 n。每一次抽卡，她获得第 i 种卡牌的概率为 pi。如果这张卡牌之前已经获得过了，就会转化为一枚硬币。可以用 k 枚硬币交换一张没有获得过的卡。

小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。如果你给出的答案与标准答案的绝对误差不超过 10−4，则视为正确。

提示：聪明的小林会把硬币攒在手里，等到通过兑换就可以获得剩余所有卡牌时，一次性兑换并停止抽卡。

输入格式

从标准输入读入数据。

输入共两行。第一行包含两个用空格分隔的正整数 n,k，第二行给出 p1,p2,…,pn，用空格分隔。

输出格式

输出到标准输出。

输出共一行，一个实数，即期望抽卡次数。

样例1输入

2 2

0.4 0.6

Data

样例1输出

2.52

Data

样例1解释

共有 2 种卡牌，不妨记为 A 和 B，获得概率分别为 0.4 和 0.6，2 枚硬币可以换一张卡牌。下面给出各种可能出现的情况：

第一次抽卡获得 A，第二次抽卡获得 B，抽卡结束，概率为 0.4×0.6=0.24，抽卡次数为 2。

第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 B，抽卡结束，概率为 0.4×0.4×0.6=0.096，抽卡次数为 3。

第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 A，用硬币兑换 B，抽卡结束，概率为 0.4×0.4×0.4=0.064，抽卡次数为 3。

第一次抽卡获得 B，第二次抽卡获得 A，抽卡结束，概率为 0.6×0.4=0.24，抽卡次数为 2。

第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 A，抽卡结束，概率为 0.6×0.6×0.4=0.144，抽卡次数为 3。

第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 B，用硬币兑换 A，抽卡结束，概率为 0.6×0.6×0.6=0.216，抽卡次数为 3。

因此答案是 0.24×2+0.096×3+0.064×3+0.24×2+0.144×3+0.216×3=2.52。

样例2输入

4 3

0.006 0.1 0.2 0.694

Data

样例2输出

7.3229920752

Data

子任务

对于 20% 的数据，保证 1≤n,k≤5。

对于另外 20% 的数据，保证所有 pi 是相等的。

对于 100% 的数据，保证 1≤n≤16,1≤k≤5，所有的 pi 满足 pi≥110000，且 ∑i=1npi=1。

#include <bits/stdc++.h>
using namespace std;

const int maxstate = 65536 + 5;
const int maxnk = 80 + 5;

int n, k;
double p[20];

int calcCard(int mask) {
  int ret = 0;
  for (int i = 0; i < n; i++) {
    if (mask & (1<<i)) {
      ret++;
    }
  }
  return ret;
}

double dp[maxstate][maxnk];

int main() {


  cin >> n >> k;
  for (int i = 0; i < n; i++) scanf("%lf",&p[i]);

  int mask = (1<<n)-1;
  for(int i=0;i<=n-1;++i){
    dp[1<<i][0]=p[i];


  }




  double ans = 0;
  for (int s = 1; s <= mask; s++) {
    for (int j = 0; j < n*k; j++) {
      int cards = calcCard(s);
      if (cards + j/k >= n) {
          ans += dp[s][j] * (cards + j);
          continue;
      }
      for (int i = 0; i < n; i++) {
        if (s & (1<<i)) {
          dp[s][j+1] += dp[s][j] * p[i];
        } else {
          dp[s|(1<<i)][j] += dp[s][j] * p[i];
        }
      }
    }
  }
  printf("%.10lf", ans);//直到改成10的长度才过了
  return 0;
}

特别鸣谢


https://blog.csdn.net/weixin_43398681/article/details/120500749



https://www.cnblogs.com/lipoicyclic/p/15354993.html

二刷，对状态里的1的计数有所改进

#include<iostream>
#include<cstdio>
#include<algorithm>
#define go(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
double dp[(1<<17)-1][16*5];
int one[(1<<17)-1];
double p[20];

void init_one(int sm){ go(s,1,sm)one[s]=one[s&(s-1)]+1; }




int main(){
int n,k;
cin>>n>>k;
int sm=(1<<n)-1;
go(i,0,n-1){
scanf("%lf",&p[i]);
dp[1<<i][0]=p[i];
}


init_one(sm);

double ans=0;

go(s,1,sm){
    go(j,0,n*k-1){
       if(one[s]+j/k>=n){
            ans+= (one[s]+j)*dp[s][j];
            continue;//请注意此处是continue
       }
       go(i,0,n-1){
            if(s&(1<<i))
               dp[s][j+1]+=dp[s][j]* p[i];
            else
                dp[s|(1<<i)][j]+=dp[s][j]* p[i];

        }

    }
}


printf("%.10lf",ans);

return 0;
}