題目連結:HDU5753
Permutation Bo
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 451 Accepted Submission(s): 269
Special Judge
Problem 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
題意:2個序列h1~hn,c1~cn,第一個是1到n的一個排列,ans是c1到cn的連加,如果ci對應的hi比它周圍2個數都大的話就去ci的值,否則不取。問結果的期望是多少。
題目分析:先求每個點取的機率,兩邊的點隻與1個數比較,是以機率1/2,中間的點與2個數比較,機率1/3;之後求期望即可。注意對1的特判。
//
// main.cpp
// Permutation Bo
//
// Created by teddywang on 2016/7/27.
// Copyright © 2016年 teddywang. All rights reserved.
//
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
int n;
double ans,buf;
while(cin>>n)
{
ans=0;
if(n==1)
{
cin>>buf;
printf("%.6lf\n",buf);
}
else
{
for(int i=0;i<n;i++)
{
cin>>buf;
if(i==0||i==n-1)
{
ans+=buf/2;
}
else ans+=buf/3;
}
printf("%.6lf\n",ans);
}
}
}