235B - Let's Play Osu!
Let us take a deep look in how this score is calculated. for a n long 'O' block, they contribute n2 to
answer.
Let us reformat this problem a bit and consider the following problem.
For each two 'O' pair which is no 'X' between them, they add 2 to score.
For each 'O',it add 1 to score.
We can see that these two problem are exact the same.
Proof:
for a n long 'O' block,there is Cn2 pair
of 'O' in it and n 'O' in it.
2Cn2 + n = n2.
So for each event(i,j) (which means s[i] and s[j] are 'O', and there's no 'X' between them).
If event(i,j) happen, it add 2 to the score.
So we only sum up the probability of all events and multiply them by 2.
Then our task become how to calculate the sum of all event(i,j).
We can see event(i,j) is simpliy .
Then we denote dp(j) as sum of all event(i,j) and i<j.
so dp(0)=0 and dp(j)=(dp(j-1)+pj - 1)*pj
/** * Created by ckboss on 14-9-3. */ import java.util.*; public class N { public static void main(String[] args){ Scanner in=new Scanner(System.in); int n=in.nextInt(); double ans=0,pre=0,now=0; for(int i=1;i<=n;i++) { now=in.nextDouble(); pre=pre*now; ans+=2*pre+now; pre=pre+now; } System.out.println(ans); } }