백준25994 Crashing Competition Computer

작성일 | In

문제 링크

  • http://icpc.me/25994

문제 출처

  • 2022 BAPC C번

사용 알고리즘

  • DP

시간복잡도

  • $O(N^2)$

풀이

저장하지 않고 $i$글자를 입력하기 위해 필요한 시간의 기댓값을 $C(i)$라고 합시다. $C(i) = C(i-1) + 1 + P\times (R+C(i))$이고, 식을 전개하면 $(1-P)C(i) = C(i-1) + 1 + PR$을 얻을 수 있습니다. 따라서 $C(i) = (C(i-1) + 1 + PR) / (1 - P)$입니다.
$i$번째 글자까지 입력하기 위해 필요한 시간의 기댓값은 $D(i) = \min_{0\leq j<i}\left{ D(j) + C(i-j) + T \right}$를 이용해 $O(N^2)$ 시간에 계산할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
using ld = double;

int N, T, R; // number, save, crash
ld P, C[2020], D[2020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T >> R >> P; P = 1 - P;
    for(int i=1; i<=N; i++){
        C[i] = (C[i-1] + 1 + (1 - P) * R) / P;
    }
    for(int i=1; i<=N; i++) D[i] = 1e18;
    for(int i=1; i<=N; i++){
        for(int j=0; j<i; j++) D[i] = min(D[i], D[j] + C[i-j] + T);
    }
    cout << fixed << setprecision(10) << D[N];
}