Permutation Bo

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5753

Description

There are two sequences h1∼hn and c1∼cn. h1∼hn is a permutation of 1∼n. particularly, h0=hn+1=0.

We define the expression [condition] is 1 when condition is True,is 0 when condition is False.

Define the function f(h)=∑ni=1ci[hi>hi−1 and hi>hi+1]

Bo have gotten the value of c1∼cn, and he wants to know the expected value of f(h).

Input

This problem has multi test cases(no more than 12).

For each test case, the first line contains a non-negative integer n(1≤n≤1000), second line contains n non-negative integer ci(0≤ci≤1000).

Output

For each test cases print a decimal - the expectation of f(h).

If the absolute error between your answer and the standard answer is no more than 10−4, your solution will be accepted.

Sample Input

4

3 2 4 5

5

3 5 99 32 12

Sample Output

6.000000

52.833333

Hint

题意

给你c数组，如果h[i]>h[i-1]和h[i]>h[i+1]，答案就加上c。

h是1-n的排列，h[0]=0,h[n+1]=0

然后求最后答案的期望是多少

题解：

根据期望的线性性，我们可以分开考虑每个位置对答案的贡献。

可以发现当ii不在两边的时候和两端有六种大小关系，其中有两种是对答案有贡献的。

那么对答案的贡献就是\(\frac{c_i}{3}\)

在两端的话有两种大小关系，其中有一种对答案有贡献。

那么对答案的贡献就是\(\frac{c_i}{2}\)

复杂度是O(n)。

注意特判n=1的情况。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1005;

int n;

int c[maxn];

void solve(){

    for(int i=1;i<=n;i++)

        scanf("%d",&c[i]);

    if(n==1){

        double ans = c[1];

        printf("%.12f\n",ans);

        return;

    }

    if(n==2){

        double ans = (c[1]+c[2])/2.0;

        printf("%.12f\n",ans);

        return;

    }

    double ans = 0;

    for(int i=2;i<n;i++)

        ans += (c[i])/3.0;

    ans+=c[1]/2.0;

    ans+=c[n]/2.0;

    printf("%.12f\n",ans);

}

int main(){

    while(scanf("%d",&n)!=EOF)solve();

    return 0;

}