Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <cmath>
- #include <map>
- #include <cstring>
- #include <iomanip>
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #define forr(i,x,n) for(int i=(x); i<int(n); i++)
- #define forn(i,n) forr(i,0,n)
- using namespace std;
- typedef long long ll;
- typedef double real;
- const ll MAXN = 2005;
- const real INF = 1e9;
- ll N;
- vector<real> C(MAXN);
- real LSUM[MAXN];
- real RSUM[MAXN];
- real DP[MAXN][MAXN][2];
- real f(int s, int e, int b){
- if(DP[s][e][b] >= 0) return DP[s][e][b];
- real ans = INF;
- real denom = LSUM[s-1] + RSUM[e];
- if(b == 0){
- if(s > 0) ans = min(ans, (1 - C[s-1]/denom) * ( f(s-1, e, 0) + 1 ) + 1 * C[s-1]/denom);
- if(e < 2*N) ans = min(ans, ( f(s, e+1, 1) + (e-s+1) ) * (1 - C[e]/denom) + (e-s+1) * C[e]/denom);
- }else{
- if(s > 0) ans = min(ans, (1 - C[s-1]/denom) * ( f(s-1, e, 0) + (e-s+1) ) + (e-s+1) * C[s-1]/denom);
- if(e < 2*N) ans = min(ans, ( f(s, e+1, 1) + 1 ) * (1 - C[e]/denom) + C[e]/denom);
- }
- return DP[s][e][b] = ans;
- }
- int main(){
- ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- //freopen("in.txt", "r", stdin);
- cin>>N;
- forn(i,2*N+1) forn(j,2*N+1) forn(b,2) DP[i][j][b] = -1;
- forn(b,2) DP[0][2*N][b] = 0;
- forn(i, 2*N) cin >> C[i];
- LSUM[0] = C[0];
- forr(i, 1, 2*N)
- LSUM[i] = LSUM[i-1] + C[i];
- RSUM[2*N-1] = C[2*N-1];
- for(int i = 2*N-2; i >=0; i--)
- RSUM[i] = RSUM[i+1] + C[i];
- cout << fixed << showpoint << setprecision(6) << f(N, N, 0) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement