티스토리 뷰

문제 풀이

[CF 146 B] Let's Play Osu!

RiKang 2017. 10. 31. 17:28

m^2 = m+m+m+...+m (총 m개)  이므로


m 개의 O가 연속되어 있을 때, 한번에 m^2을 획득한 게 아니라


m 번의 클릭(O) 이 각각 m 점을 획득한 것이라고 바꿔 생각할 수 있다.


이러면, 정답 = ∑ ( i 번째 클릭이 얻은 점수의 기댓값) = ∑ ( i 번째 클릭이 속한 O 그룹의 길이의 기댓값) 이 된다.


이제 쉽게 DP를 설정해보면,


DP[i] = i 번째가 클릭이 속한 O 그룹의 길이의 기댓값.


그런데 이 DP[i] 를 구하려고 해보면


(i-1) 번째 클릭의 성공률이 DP[i] 에 영항을 끼치고,  i 번째 클릭의 성공률이 DP[i-1]에 영향을 끼쳐서


결국 상호 간에 영향을 끼치기 때문에 까다로워짐을 알 수 있다.


DP[i] 의 부분 문제로 DP[i-1]을 설정해놓고, DP[i-1]의 부분 문제로 그 상위 문제인 DP[i]를 설정하긴 힘들기 때문이다.


이를 해소하기 위해서 DP[i]를 분해하면,


left[i] = i 번째가 클릭이 속한 O 그룹 중 'i의 오른쪽' 길이의 기댓값.

right[i] = i 번째가 클릭이 속한 O 그룹 중 'i의 왼쪽' 길이의 기댓값.


이와 같이 설정할 수 있다.


left[i] 의 부분 문제로는 left[i-1], right[i] 의 부분 문제로는 right[i+1] 로 루프 없이 부분 문제를 설정할 수 있다.


left[i] 와 left[i-1]의 관계는 수학적으로 간단.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// code by RiKang, weeklyps.com
#include<stdio.h>
 
const int N = 100000;
int n;
double a[N+5];
double left[N+5];
double right[N+5];
double ans;
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf",&a[i]);
    a[0]=a[n+1]=0;
    for(int i=1;i<=n;i++)
        left[i]=(left[i-1]+1)*a[i];
    for(int i=n;i>=1;i--)
        right[i]=(right[i+1]+1)*a[i];
    for(int i=1;i<=n;i++)
        ans+=a[i]*(1+left[i-1]+right[i+1]);
    printf("%.9lf",ans);
    return 0;
}
cs


'문제 풀이' 카테고리의 다른 글

[CF 371 D] Animals and Puzzle  (0) 2017.10.31
[BOJ 4008] 특공대  (0) 2017.10.31
[CF 146 B] Let's Play Osu!  (0) 2017.10.31
[BOJ 2533] 사회망 서비스  (0) 2017.10.31
[BOJ 5060] 무글 맵스  (0) 2017.10.31
[BOJ 2057] 계단 오르기  (0) 2017.10.31