Permutation Bo

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 699    Accepted Submission(s): 427
Special Judge


Problem Description
There are two sequences h1hn and c1cn. h1hn is a permutation of 1n. 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>hi1  and  hi>hi+1]

Bo have gotten the value of c1cn, 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(1n1000), second line contains n non-negative integer ci(0ci1000).
 

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 104, your solution will be accepted.
 

Sample Input
4 3 2 4 5 5 3 5 99 32 12
 

Sample Output
6.000000 52.833333
 

Author
绍兴一中
 

Source


思路:
这道题的思路其实很简单,就是每个ci对应一个hi,如果hi>hi+1&&hi>hi-1,那么f(h)就加上ci,如果不满足则这一项ci就不加。我们思维定式的求和是先求出每一个f(h),然后再相加。但是这个题这么做是做不出来的,只能转变思维,对每个元素进行求和,再对所有元素加起来。就比如c1,它可能在f(h1)中能加上,在f(h2)中就加不上,所以对ci先求和。
从第一个位置开始看,如果能加上的话,那么h1>h0=0&&h1>h2,所以先从n个数中选取两个数,它们会自动生成大小关系,那么把大数放在第一位,小数放第二位,其他的位置自由组合A(n-2,n-2),总共有A(n,n)种情况,所以第一个位置加上c1的概率就是C(n,2)*A(n-2,n-2)/A(n,n)=1/2。由于对称性,最后一位也是这样。
接下来看中间三位,也是同样的做法,先从n个数中选取3个数,它们会自动生成大小关系,那么把最大数放在中间位,另外两个数自由排列A(2,2),其他的位置自由组合A(n-3,n-3),总共有A(n,n)种情况,所以中间三位的情况下第i个位置加上ci的概率就是C(n,3)*A(2,2)*A(n-3,n-3)/A(n,n)=1/3。
也就是说,两头的c加上的概率是1/2,中间的加上c的概率是1/3。这就可以求解了。


代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
#define N 1005
#define LL long long

int n,c[N];
LL tot,v;
double ans;

int main(){
    while(scanf("%d",&n)^-1){
        rep(i,1,n) scanf("%d",c+i);
        if(n==1){printf("%.6lf\n",(double)c[1]);continue;}
        v=(LL)(n-1)*n*(2*n-1)/6-(LL)n*(n-1)/2;
        tot=0;
        ans=0;
        if(n>2){
            rep(i,2,n-1) tot+=v*c[i];
            ans+=(double)tot/(n-2)/(n-1)/n;
        }
        v=(LL)n*(n-1)/2;
        ans+=(double)(v*c[1]+v*c[n])/(n-1)/n;
        printf("%.9lf\n",ans);
    }
}