深圳市住房和建设局官方网站查询,不用写代码做的网站,曲阜人网站,怎样快速学好网站建设4009.收集卡牌
4009. 收集卡牌 - AcWing题库难度#xff1a;困难时/空限制#xff1a;1s / 512MB总通过数#xff1a;995总尝试数#xff1a;1852来源#xff1a;第23次CCF计算机软件能力认证算法标签数学期望DP状态压缩DP记忆化搜索 题目内容
小林在玩一个抽卡游戏困难时/空限制1s / 512MB总通过数995总尝试数1852来源第23次CCF计算机软件能力认证算法标签数学期望DP状态压缩DP记忆化搜索 题目内容
小林在玩一个抽卡游戏其中有 n 种不同的卡牌编号为 1 到 n。 每一次抽卡她获得第 i 种卡牌的概率为 pi。 如果这张卡牌之前已经获得过了就会转化为一枚硬币。 可以用 k 枚硬币交换一张没有获得过的卡。 小林会一直抽卡直至集齐了所有种类的卡牌为止求她的期望抽卡次数。 如果你给出的答案与标准答案的绝对误差不超过 1 0 − 4 10^{-4} 10−4则视为正确。 提示聪明的小林会把硬币攒在手里等到通过兑换就可以获得剩余所有卡牌时一次性兑换并停止抽卡。
输入格式
输入共两行。 第一行包含两个用空格分隔的正整数 n,k第二行给出 p1,p2,…,pn用空格分隔。
输出格式
输出共一行一个实数即期望抽卡次数。
数据范围
对于 20% 的数据保证 1≤n,k≤5。 对于另外 20% 的数据保证所有 pi 是相等的。 对于 100% 的数据保证 1≤n≤16,1≤k≤5所有的 pi 满足 pi≥1/10000且 ∑ i 1 n \sum_{i1}^n ∑i1n pi1。 注意本题在官网必须保留 10 位小数才能通过可能是没加SPJ在本网站无此问题只要满足你给出的答案与标准答案的绝对误差不超过 1 0 − 4 10^{-4} 10−4则视为正确。
输入样例1
2 2
0.4 0.6输出样例1
2.52样例1解释
共有 2 种卡牌不妨记为 A 和 B获得概率分别为 0.4 和 0.62 枚硬币可以换一张卡牌。下面给出各种可能出现的情况
第一次抽卡获得 A第二次抽卡获得 B抽卡结束概率为 0.4×0.60.24抽卡次数为 2。第一次抽卡获得 A第二次抽卡获得 A第三次抽卡获得 B抽卡结束概率为 0.4×0.4×0.60.096抽卡次数为 3。第一次抽卡获得 A第二次抽卡获得 A第三次抽卡获得 A用硬币兑换 B抽卡结束概率为 0.4×0.4×0.40.064抽卡次数为 3。第一次抽卡获得 B第二次抽卡获得 A抽卡结束概率为 0.6×0.40.24抽卡次数为 2。第一次抽卡获得 B第二次抽卡获得 B第三次抽卡获得 A抽卡结束概率为 0.6×0.6×0.40.144抽卡次数为 3。第一次抽卡获得 B第二次抽卡获得 B第三次抽卡获得 B用硬币兑换 A抽卡结束概率为 0.6×0.6×0.60.216抽卡次数为 3。
因此答案是 0.24×20.096×30.064×30.24×20.144×30.216×32.52
输入样例2
4 3
0.006 0.1 0.2 0.694输出样例2
7.3229920752题目解析
最后用硬币兑换没有出现过的卡牌
n表示卡牌总共的种类 k表示多少枚硬币换一张卡牌
第二行是每次抽到每张卡牌的概率
输出期望抽卡次数
非常经典的在算法题里常见的数学期望问题‘
从数学期望的角度分析
n很小表示状态的时候需要用状态压缩的思想
如何表示状态
假设n5现在的卡牌有245硬币的数量是2 因为n很小只有16表示有哪些卡牌的时候可以用一个压缩的状态用一个5位的01串来表示01011分别表示这5张卡牌有没有 用第二个数表示硬币数 所以状态可以用 ( 01011 , 2 ) (01011,2) (01011,2)的二维状态来表示 写代码的时候把01串看成是二进制表示转化成对应的十进制数来存储
从当前这个状态直到集齐所有卡牌这个过程在概率论里面称为事件
需要找一下不同事件之间的关系
比如 ( 01011 , 2 ) (01011,2) (01011,2)可以转化成哪些事件呢 就看下一抽能抽到什么卡牌 一共有五种抽发所以能变成五种事件概率分别是 p 1 , p 2 , p 3 , p 4 , p 5 p_{1},p_{2},p_{3},p_{4},p_{5} p1,p2,p3,p4,p5 如果下一抽抽的是第一张卡牌的话变成的事件分别是 X 1 X 2 , X 3 , X 4 , X 5 X_{1}X_{2},X_{3},X_{4},X_{5} X1X2,X3,X4,X5 X 1 X_{1} X1是 ( 11011 , 2 ) (11011,2) (11011,2) X 2 X_{2} X2是 ( 01011 , 3 ) (01011,3) (01011,3) X 3 X_{3} X3是 ( 01111 , 2 ) (01111,2) (01111,2) X 4 X_{4} X4是 ( 01011 , 3 ) (01011,3) (01011,3) X 5 X_{5} X5是 ( 01011 , 3 ) (01011,3) (01011,3) 设初始事件是 X X X会被5种不同的概率分辨成5种事件 当然在变成 X 1 X_{1} X1的时候需要付出1抽的代价 所以期望是加1的因为要多一步
这几个事件之间的关系 X P 1 ( X 1 1 ) ⋯ P n ( X n 1 ) XP_{1}(X_{1}1)\dotsP_{n}(X_{n}1) XP1(X11)⋯Pn(Xn1) E ( x ) E ( P 1 ( X 1 1 ) ⋯ P n ( X n 1 ) ) E(x)E(P_{1}(X_{1}1)\dotsP_{n}(X_{n}1)) E(x)E(P1(X11)⋯Pn(Xn1)) 要找的是 E ( x 1 ) E(x_{1}) E(x1)到 E ( x 2 ) E(x_{2}) E(x2)一直到 E ( x 5 ) E(x_{5}) E(x5)之间的关系 但是 E ( x ) E(x) E(x)里面还有其他的项又有乘法又有加法 要用期望的运算性质把它展开整理一下
期望的运算性质 E ( C ) C E ( C X ) C E ( x ) E ( X Y ) E ( x ) E ( Y ) \begin{array}{} E(C)C \\ E(CX)CE(x) \\ E(XY)E(x)E(Y) \end{array} E(C)CE(CX)CE(x)E(XY)E(x)E(Y) E ( x ) E ( P 1 ( X 1 1 ) ) ⋯ E ( P n ( X n 1 ) P 1 E ( X 1 1 ) ⋯ P n E ( X n 1 ) \begin{array}{} E(x)E(P_{1}(X_{1}1))\dotsE(P_{n}(X_{n}1) \\ P_{1}E(X_{1}1)\dotsP_{n}E(X_{n}1) \end{array} E(x)E(P1(X11))⋯E(Pn(Xn1)P1E(X11)⋯PnE(Xn1) x可以看成一个随机变量相当于这个事件发生的概率是100% P 1 ( E ( X 1 ) E ( 1 ) ) ⋯ P n ( E ( X n ) E ( 1 ) ) P 1 ( E ( X 1 ) 1 ) ⋯ P n ( E ( X n ) 1 ) \begin{array}{} P_{1}(E(X_{1})E(1))\dotsP_{n}(E(X_{n})E(1)) \\ P_{1}(E(X_{1})1)\dotsP_{n}(E(X_{n})1) \end{array} P1(E(X1)E(1))⋯Pn(E(Xn)E(1))P1(E(X1)1)⋯Pn(E(Xn)1)
写代码的时候就和DP差不多了 f ( s , c ) p 1 ( f ( s 1 , c 1 ) 1 ) ⋯ p n ( f ( s n , c n ) 1 ) f(s,c)p_{1}(f(s_{1},c_{1})1)\dotsp_{n}(f(s_{n},c_{n})1) f(s,c)p1(f(s1,c1)1)⋯pn(f(sn,cn)1) 可以看成一个DP问题
状态数量
第一维有16位每一位有2种取法2^16 第二维最多是每5个硬币换一张卡牌所以k不可能大于80 因为如果有80个硬币就可以换所有卡牌 一共是500多万个状态
每次算每个状态的时候右边会有n项8000万的计算量 而且有的状态是没有意义的达不到的
用记忆化搜索来写 可以搜不到用不到的状态 数学期望是用DP来存的期望的定义和DP是差不多的 如果不了解数学期望可以把一个随机变量看成是一个集合 接下来就从集合角度分析DP问题
每一个事件可以看成一个集合 从当前状态集完所有卡牌的事件可以看成一个集合 抽五次的概率p1 抽六次的概率p2 … 左边一列是抽取的次数右边一列是对应的概率 可以把这个集合看成是随机变量
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 16, M 1 N;
//M表示每一种卡牌手里有没有int n, m;
//p表示每种卡牌抽到的概率f表示状态
double p[N], f[M][N * 5 1];double dp(int state, int coins, int r)
{//用v来表示当前状态double v f[state][coins];//如果v大于等于0表示这个状态算过了if (v 0) return v;//否则判断一下当前缺少的卡牌数量//如果硬币能够兑换剩下的返回不需要再抽了if (coins r * m) return v 0;//否则计算当前状态v 0;for (int i 0; i n; i )//如果当前状态已经有这种卡牌了if (state i 1)v p[i] * (dp(state, coins 1, r) 1);else//如果没有这种卡牌的话获得这张卡牌v p[i] * (dp(state | (1 i), coins, r-1) 1);//多了一种没有用的卡牌缺的卡牌数量应该减1return v;
}int main()
{scanf(%d%d, n, m);//读入每种卡牌抽到的概率for (int i 0; i n; i ) scanf(%lf, p[i]);//先将所有状态初始化成-1memset(f, -1, sizeof f);//输出一下一张卡牌也没有硬币也是0的状态printf(%.10lf\n, dp(0, 0, n));//n表示一开始state有n位是0return 0;
}
