Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int n;
- vector<double> p;
- vector<double> dp;
- double sim(int m)
- {
- if(dp[m]!=-1) return dp[m];
- int numLeft = 0;
- for(int i=0;i<n;i++)
- {
- if((m>>i) & 1) continue;
- numLeft++;
- }
- if(numLeft<=2) return dp[m] = 0;
- double pAllUp = 1;
- double pAllDown = 1;
- for(int i=0;i<n;i++)
- {
- if((m>>i) & 1) continue;
- pAllUp *= p[i];
- pAllDown *= (1-p[i]);
- }
- double pElimination = 0;
- for(int i=0;i<n;i++)
- {
- if( (m>>i) & 1 ) continue;
- pElimination += pAllUp/p[i] * (1-p[i]);
- pElimination += pAllDown/(1-p[i]) * p[i];
- }
- double ev = 1/pElimination;
- for(int i=0;i<n;i++)
- {
- if( (m>>i) & 1 ) continue;
- double piEliminated = pAllUp/p[i] * (1-p[i]) + pAllDown/(1-p[i]) * p[i];
- ev += piEliminated / pElimination * sim( m | (1<<i) );
- }
- return dp[m] = ev;
- }
- int main()
- {
- cin >> n;
- p.resize(n);
- for(int i=0;i<n;i++) cin >> p[i];
- dp.resize(1<<n, -1);
- printf("%.10f\n", sim(0));
- }
Advertisement
Add Comment
Please, Sign In to add comment