蓝桥杯试题 算法训练 印章 (dp&详解) |
您所在的位置:网站首页 › 算法如何训练数学题 › 蓝桥杯试题 算法训练 印章 (dp&详解) |
试题 算法训练 印章
提交此题 评测记录 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。 输入格式 一行两个正整数n和m 输出格式 一个实数P表示答案,保留4位小数。 样例输入 2 3 样例输出 0.7500 数据规模和约定 1≤n,m≤20 解题思路: n种图案,m张印章,概率为p=1/n,这个题因为情况不一样,所以我们可以分情况来看。 首先:dp[i][j]就代表i张印章凑齐j种图案的概率 然后我们先来看一般情况: 1) i1,我们每个图案的概率都是dp[i][1]= p^i;因为我们的图案不指定哪一种,所以我们的dp[i][j]是n种图案的概率之和,就是p^i*n;因为p=1/n;所以就是p^(i-1) 接着我们看其它的情况: 3) 因为我们的凑的印章不规定是哪一种图案,所以我们dp记录我们概率值的时候,就得分情况:要么是有重复的(j已经凑齐了),要么是没重复的(还有没凑齐的)有重复的:表示前面的 i-1 张里面已经凑齐了 j 种,第 i 张就是重复前面的印章,这个时候前面已经出现过的 j 种印章再出现的时候,它就是 j*p 这个时候dp[i][j] = dp[i-1][j] * (j/n) = dp[i-1][j] *(j*p) 无重复的:表示前 i-1 张凑齐了 j-1 种,其中,第 i 张就是最后的一种要凑的,因为题目不规定具体求那一种图案的概率,所以我们只需要乘以前面没出现过的印章再出现的概率,因为前面已经出现了 j-1 种了,所以我们剩下没出现的就是 n-(j-1) 种,只要是其中的一种就行了,这个时候凑齐最后一种的概率就是 (n-j+1)*p 这个时候dp[i][j] = dp[i-1][j-1]*(n-(j-1))/n = dp[i-1][j-1]*(n-j+1)*p 我们只需要把这两种情况相加即可。 最后只需要输出我们要求的dp[m][n] 就可以了。 AC #include #include #include #include #include using namespace std; double dp[30][30]; int main(void) { int n,m; cin>>n>>m; double p=1.0/n; memset(dp,0,sizeof(dp)); for(int i=1;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |