196722025-12-18 14:46:37diakHullámvasút építéscpp17Accepted 100/1002ms876 KiB
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string S;
    cin >> S;

    // dp[i][v] = min csere, i szakasz után v sebességgel
    // Max sebesség becslés: 100 * 10 = 1000 elég
    const int MAXV = 1000;
    vector<vector<int>> dp(N + 1, vector<int>(MAXV + 1, INF));

    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        for (int v = 0; v <= MAXV; v++) {
            if (dp[i][v] == INF) continue;

            char c = S[i];
            if (c == 'D') {
                int nv = v + 9;
                if (nv > 0 && nv <= MAXV)
                    dp[i + 1][nv] = min(dp[i + 1][nv], dp[i][v]);
            }
            else if (c == 'B') {
                int nv = v + 10;
                if (nv > 0 && nv <= MAXV)
                    dp[i + 1][nv] = min(dp[i + 1][nv], dp[i][v]);
            }
            else if (c == 'U') {
                int nv = v - 11;
                if (nv > 0)
                    dp[i + 1][nv] = min(dp[i + 1][nv], dp[i][v]);
            }
            else if (c == 'H') {
                // H marad
                if (v > 0)
                    dp[i + 1][v] = min(dp[i + 1][v], dp[i][v]);

                // H -> B csere
                int nv = v + 10;
                if (nv > 0 && nv <= MAXV)
                    dp[i + 1][nv] = min(dp[i + 1][nv], dp[i][v] + 1);
            }
        }
    }

    int ans = INF;
    for (int v = 1; v <= MAXV; v++) {
        ans = min(ans, dp[N][v]);
    }

    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms500 KiB
2Accepted2ms316 KiB
3Accepted2ms316 KiB
subtask210/10
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms564 KiB
8Accepted1ms564 KiB
9Accepted1ms820 KiB
subtask315/15
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms564 KiB
14Accepted1ms564 KiB
15Accepted1ms820 KiB
16Accepted1ms756 KiB
17Accepted1ms316 KiB
18Accepted1ms564 KiB
19Accepted1ms756 KiB
20Accepted1ms316 KiB
subtask420/20
21Accepted1ms316 KiB
22Accepted1ms316 KiB
23Accepted1ms564 KiB
24Accepted1ms716 KiB
25Accepted1ms564 KiB
26Accepted1ms580 KiB
27Accepted1ms316 KiB
28Accepted1ms564 KiB
29Accepted1ms876 KiB
30Accepted1ms564 KiB
31Accepted1ms316 KiB
32Accepted2ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
subtask520/20
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms564 KiB
38Accepted1ms716 KiB
39Accepted1ms564 KiB
40Accepted1ms580 KiB
41Accepted1ms316 KiB
42Accepted1ms564 KiB
43Accepted1ms876 KiB
44Accepted1ms564 KiB
45Accepted1ms316 KiB
46Accepted2ms316 KiB
47Accepted1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms580 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Accepted1ms316 KiB
54Accepted2ms784 KiB
55Accepted2ms564 KiB
56Accepted1ms776 KiB
57Accepted1ms564 KiB
58Accepted1ms564 KiB
59Accepted1ms564 KiB
subtask635/35
60Accepted1ms316 KiB
61Accepted1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms564 KiB
67Accepted1ms564 KiB
68Accepted1ms820 KiB
69Accepted1ms756 KiB
70Accepted1ms316 KiB
71Accepted1ms564 KiB
72Accepted1ms756 KiB
73Accepted1ms316 KiB
74Accepted1ms316 KiB
75Accepted1ms316 KiB
76Accepted1ms564 KiB
77Accepted1ms716 KiB
78Accepted1ms564 KiB
79Accepted1ms580 KiB
80Accepted1ms316 KiB
81Accepted1ms564 KiB
82Accepted1ms876 KiB
83Accepted1ms564 KiB
84Accepted1ms316 KiB
85Accepted2ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms580 KiB
89Accepted1ms316 KiB
90Accepted1ms316 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
93Accepted2ms784 KiB
94Accepted2ms564 KiB
95Accepted1ms776 KiB
96Accepted1ms564 KiB
97Accepted1ms564 KiB
98Accepted1ms564 KiB
99Accepted1ms332 KiB
100Accepted1ms564 KiB
101Accepted1ms508 KiB
102Accepted1ms420 KiB
103Accepted1ms316 KiB
104Accepted1ms564 KiB
105Accepted1ms316 KiB
106Accepted2ms680 KiB
107Accepted2ms564 KiB
108Accepted1ms564 KiB
109Accepted2ms564 KiB
110Accepted1ms316 KiB
111Accepted1ms316 KiB
112Accepted1ms336 KiB
113Accepted2ms564 KiB
114Accepted1ms564 KiB