FZOJ Problem 2103 Bin & Jing in wonderland
Problem 2103 Bin & Jing in wonderland
Accept: 221 Submit: 1175
Time Limit: 1000 mSec Memory Limit : 32768
KB
Problem Description
Bin has a dream that he and Jing are both in a wonderland full of beautiful
gifts. Bin wants to choose some gifts for Jing to get in her good graces.
There are N different gifts in the wonderland, with ID from 1 to N, and all
kinds of these gifts have infinite duplicates. Each time, Bin shouts loudly, “I
love Jing”, and then the wonderland random drop a gift in front of Bin. The
dropping probability for gift i (1≤i≤N) is P(i). Of cause, P(1)+P(2)+…+P(N)=1.
Bin finds that the gifts with the higher ID are better. Bin shouts k times and
selects r best gifts finally.
That is, firstly Bin gets k gifts, then sorts all these gifts according to
their ID, and picks up the largest r gifts at last. Now, if given the final list
of the r largest gifts, can you help Bin find out the probability of the
list?
Input
The first line of the input contains an integer T (T≤2,000), indicating
number of test cases.
For each test cast, the first line contains 3 integers N, k and r (1≤N≤20,
1≤k≤52, 1≤r≤min(k,25)) as the description above. In the second line, there are N
positive float numbers indicates the probability of each gift. There are at most
3 digits after the decimal point. The third line has r integers ranging from 1
to N indicates the finally list of the r best gifts’ ID.
Output
decimal points, which indicates the probability of the final list.
Sample Input
2 3 3
0.3 0.7
1 1 1
2 3 3
0.3 0.7
1 1 2
2 3 3
0.3 0.7
1 2 2
2 3 3
0.3 0.7
2 2 2
Sample Output
0.189000
0.441000
0.343000
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N_MAX = ;
int N, k, r;
double P[N_MAX];
int res[N_MAX];
int num[N_MAX];
ll C[][];
void C_table(){
for (int i = ; i < ;i++) {
C[i][] = C[i][i] = ;
for (int j = ; j < i;j++) {
C[i][j] = C[i-][j] + C[i-][j-];
}
}
} double all_position() {
double ans = ;
int number = k;
for (int i = ; i <= N;i++) {//把所有已经知道的数放进k个位置中相应的位置所有的放法
if (num[i]) {
ans *= C[number][num[i]];
number -= num[i];
}
}
return ans;
} int main() {
int T;
scanf("%d",&T);
C_table();//组合排列查询表
while (T--) {
memset(num,,sizeof(num));
scanf("%d%d%d",&N,&k,&r);
for (int i = ; i <= N;i++)
scanf("%lf",&P[i]);
double u = ,p=,ans=;
for (int i = ; i <= r; i++) {
scanf("%d", &res[i]);
num[res[i]]++;//记录该礼物的数量
u *= P[res[i]];//把已知的那些礼物的概率累乘得到的是一种情况下这些礼物的放置位置,再乘上所有可能的放置位置就得到这部分礼物概率
}
sort(res+,res+r+);
for (int i = ; i < res[];i++) {//把编号比res[1]还小的礼物的概率全部累加
p += P[i];
} for (int i = r; i <=k;i++) {
if (i > r) {
u *= P[res[]];
num[res[]]++;
}
ans += u*pow(p, k - i)*all_position(); }
printf("%.6lf\n",ans);
}
return ;
}
最新文章
- I2S/PCM/IOM-2、I2C/SPI/UART/GPIO/slimbus
- CentOS6.5菜鸟之旅:识别NTFS分区
- U_boot 的 bootcmd 和bootargs参数详解
- Namespaces(命名空间)
- Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 1) B. Bear and Blocks 水题
- ab基本用法
- SQL点滴4—筛选数据列的类型,字段大小,是否可为空,是否是主键,约束等等信息
- 提升html5的性能体验系列之三流畅下拉刷新
- Spring mybatis源码篇章-SqlSessionFactoryBean
- Spring MVC中jsessionid所引起的问题 和解决
- 用Itextsharp 组件导出PDF 的文档的方法
- pytest 8 参数化parametrize
- Debian Security Advisory(Debian安全报告) DSA-4404-1 chromium
- Kubernetes1.2如何使用iptables
- Liunx history
- UI设计教程分享:电商网页页面设计常见表现手法
- Python abs() 函数
- post注入及提权思路
- [转].net reactor 学习系列(四)---.net reactor应用场景
- JavaScript:传对象数组到后台