HDU 5753 Permutation Bo （推导 or 打表找规律）

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

Source

2016 Multi-University Training Contest 3

##题意：对于n的任意一个全排列，如果出现了hi>hi−1 && hi>hi+1 的情况，则对ci计数一次. 求所有全排列计数后，总和的期望.
##题解：先看一下官方题解：根据期望的线性性，我们可以分开考虑每个位置对答案的贡献。可以发现当i不在两边的时候和两端有六种大小关系，其中有两种是对答案有贡献的。 (比如n=3,考虑(123)(132)(213)(231)(312)(321)),仅有(132)(231)会对C2计数.) 那么对答案的贡献就是 Ci/2 在两端的话有两种大小关系，其中有一种对答案有贡献。那么对答案的贡献就是 Ci/3 复杂度是O(n)。
推不出上述规律的话还可以打表找规律：统计每个Ci出现的次数. 很容易发现C1和Cn出现的次数为n!/2; 其他Ci出现的次数是n!/3; 注意特判n=1的情况.
##代码：（注释部分为打表代码） ``` cpp #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 41000 #define mod 100000007 #define inf 0x3f3f3f3f #define IN freopen("in.txt","r",stdin); using namespace std;

int main(int argc, char const *argv[])
{
//IN;

// int n = 9;
// //int num[] = {0,1,2,3,4,0};
// //int ci[] = {0,3,2,4,5,0};
// int num[] = {0,1,2,3,4,5,6,7,8,9,0};
// int ci[] = {0,3,5,99,32,12,12,12,12,12,0};
// int cnt[10] = {0};
//
// int ans = 0;
// do{
// int cur = 0;
// for(int i=1; i<=n; i++) {
// printf("%d ", num[i]);
// if(num[i]>num[i-1] && num[i]>num[i+1]){
// cur += ci[i];
// cnt[i]++;
// }
// }
// printf(" :%d ", cur);
// ans += cur;
// }while(next_permutation(num+1,num+n+1));
//
// printf("%d ", ans);
// double Ans = (double) ans;
// for(int i=1; i<=n; i++) {
// Ans /= (double)i;
// }
// printf("%lf ", Ans);
//
// for(int i=1; i<=n; i++)
// printf("%d ", cnt[i]);

int n;
while(scanf("%d", &n) != EOF)
{
    double ans = 0;

    if(n == 1) {
        scanf("%lf", &ans);
        printf("%lf
", ans);
        continue;
    }

    for(int i=1; i<=n; i++) {
        double x; scanf("%lf", &x);
        if(i==1 || i==n) {
            ans += x / 2.0;
        } else {
            ans += x / 3.0;
        }
    }

    printf("%lf
", ans);
}

return 0;

}