钻石
diamond.in/.out/.cpp
【问题描述】
你有 n 个 “量子态” 的盒子,每个盒子里可能是一些钱也可能是一个钻 石。
现在你知道如果打开第 i 个盒子,有P i 100 Pi100 的概率能获得V i Vi 的钱,有1-P i 100 Pi100 的概率能获得一个钻石。
现在你想知道,自己恰好获得 k(0 ≤ k ≤ n) 个钻石,并且获得钱数大 于等于 m 的概率是多少。
请你对 0 ≤ k ≤ n 输出 n+1 个答案。
答案四舍五入保留 3 位小数。
【输入格式】
第一行两个整数 n,m,见题意。
接下来 n 行,每行两个整数 V i Vi , P i Pi 。
【输出格式】
输出共 n+1 行,表示 0 ≤ k ≤ n 的答案。
【样例输入】
2 3
2 50
3 50
【样例输出】
0.250
0.250
0.000
【数据规模和约定】
对于 30% 的数据, n ≤ 10。
对于 60% 的数据, n ≤ 15
对于 100% 的数据,n ≤ 30, 1 ≤ P i Pi ≤ 99, 1 ≤ V i Vi ≤ 10^7 , 1 ≤ m ≤ 10^7 。
【限制】
时间：1s
内存：256M
同样是meet in the middle 为什么差距这么大呢？？？？？ 一个20ms+ 一个1700ms+ =.=.... 1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<vector>
5 using namespace std;
6 int tt;
7 int n,m;
8 int v[35];
9 double p[35];
10 double ans[35];
11 vector<pair<int,double> > sta[35];
12 int main(){
13
14 scanf("%d%d",&n,&m);
15 for(int i=1,x;i<=n;i++){
16 scanf("%d%d",&v[i],&x);
17 p[i]=x/100.;
18 }
19 for(int i=0;i<=n;i++){
20 sta[i].clear();
21 }
22 int an=(n/2.5)+1;
23 int bn=n-an;
24 for(int st=0;st<1<<bn;st++){
25 double nowp=1;
26 int cnt=0,money=0;
27 for(int i=0;i<bn;i++){
28 if((st>>i)&1){
29 money+=v[n-i];
30 nowp*=p[n-i];
31 }else{
32 cnt++;
33 nowp*=(1-p[n-i]);
34 }
35 }
36 sta[cnt].push_back(make_pair(money,nowp));
37 }
38 for(int i=0;i<=n;i++){
39 sort(sta[i].begin(),sta[i].end());
40 for(int j=1;j<sta[i].size();j++){
41 sta[i][j].second+=sta[i][j-1].second;
42 }
43 }
44 for(int st=0;st<1<<an;st++){
45 double nowp=1;
46 int cnt=0,money=0;
47 for(int i=0;i<an;i++){
48 if((st>>i)&1){
49 money+=v[i+1];
50 nowp*=p[i+1];
51 }else{
52 cnt++;
53 nowp*=(1-p[i+1]);
54 }
55 }
56 for(int i=0;i<=bn;i++){
57 // now d =cnt+i
58 int L = m-money;
59 vector<pair<int,double> >::iterator it = lower_bound(sta[i].begin(),sta[i].end(),make_pair(L,-1.));
60 double tmp = sta[i].back().second;
61 if(it!= sta[i].begin()){
62 it--;
63 tmp-=it->second;
64 }
65 ans[cnt+i] += tmp*nowp;
66 }
67 }
68 for(int i=0;i<=n;i++){
69 printf("%.3f\n",ans[i]);
70 }
71 fclose(stdout);
72 return 0;
73 }
20ms
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<map>
6 #include<algorithm>
7 #define lli long long int
8 using namespace std;
9 const int MAXN=88000;
10 inline void read(int &n)
11 {
12 char c=getchar();n=0;bool flag=0;
13 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
14 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 struct node
17 {
18 int p,v;
19 }box[MAXN];
20 double ans[MAXN];
21 int n,m;
22 int base;// 中间节点
23 struct ANS1
24 {
25 int zuanshi;
26 int qian;
27 double gailv;
28 }ans1[MAXN];
29 int ans1tot=0;
30 struct ANS2
31 {
32 int zuanshi;
33 int qian;
34 double gailv;
35 }ans2[MAXN];
36 int ans2tot=0;
37 void dfs(int num,double gl,int money,int zs)
38 {
39 if(num==base)
40 {
41 ans1[++ans1tot].qian=money;
42 ans1[ans1tot].zuanshi=zs;
43 ans1[ans1tot].gailv=gl;
44 return ;
45 }
46 dfs(num+1,(double)gl*((double)box[num+1].p/100),money+box[num+1].v,zs);
47 dfs(num+1,(double)gl*(double)( 1 - ( (double) box[num+1].p/100) ),money,zs+1);
48 }
49 void dfs2(int num,double gl,int money,int zs)
50 {
51 if(num==n)
52 {
53 ans2[++ans2tot].qian=money;
54 ans2[ans2tot].zuanshi=zs;
55 ans2[ans2tot].gailv=gl;
56 return ;
57 }
58 dfs2(num+1,(double)gl*((double)box[num+1].p/100),money+box[num+1].v,zs);
59 dfs2(num+1,(double)gl*(double)( 1 - ( (double) box[num+1].p/100) ),money,zs+1);
60 }
61 int comp1(const ANS1 &a,const ANS1 &b)
62 {
63 return a.qian<b.qian;
64 }
65 int comp2(const ANS2 &a,const ANS2 &b)
66 {
67 return a.qian>b.qian;
68 }
69 int main()
70 {
71
72 read(n);read(m);
73 base=n/2;
74 for(int i=1;i<=n;i++)
75 {
76 read(box[i].v);
77 read(box[i].p);
78 }
79 dfs(1,(double)box[1].p/100,box[1].v,0);// 钱
80 dfs(1,(double)1-(double)box[1].p/100,0,1);// 钻石
81
82 dfs2(base+1,(double)box[base+1].p/100,box[base+1].v,0);// 钱
83 dfs2(base+1,(double)1-(double)box[base+1].p/100,0,1);// 钻石
84
85 sort(ans1+1,ans1+ans1tot,comp1);
86 sort(ans2+1,ans2+ans2tot,comp2);
87 for(int i=1;i<=ans1tot;i++)
88 {
89 for(int j=1;j<=ans2tot;j++)
90 {
91 if(ans1[i].qian+ans2[j].qian>=m)
92 ans[ans1[i].zuanshi+ans2[j].zuanshi]+=ans1[i].gailv*ans2[j].gailv;
93 else break;
94 }
95 }
96 for(int i=0;i<=n;i++)
97 printf("%.3lf\n",ans[i]);
98 return 0;
99 }
自己写的1700ms+