[Codeforces] Educational Codeforces Round 95 (Div. 2) C. Mortal Kombat Tower

2020年9月15日2020年12月13日

問題

方針

友人の行動は、ボスを倒すまたはボスをスキップすることができます。また、自分と友人は最低でも \( 1 \) 体のボスに対応しなければならなく、\( 1 \) 回のセッションで最大で \( 2 \) 体のボスを倒すことができます。

ここで友人が \( i \) 番目のボスを同一セッションで \( 1 \) 体目のボスであるときのスキップした回数を \( f(i, 0) \) とし、同一セッションで \( 2 \) 体目のボスであるときのスキップした回数を \( f(i, 1) \) とします。同様に \( g(i, 0), g(i, 1) \) を定義します。

初期値は、\( f(1, 0) = a_1\) となり、その他は \( \infty \) で初期化します。更新式は、

\begin{eqnarray}
f(i + 1, 0) &=& \min(g(i, 0), g(i, 1)) + a_{i+1}\\
f(i + 1, 1) &=& f(i, 0)+ a_{i+1}\\
g(i + 1, 0) &=& \min(f(i, 0), f(i, 1))\\
g(i + 1, 1) &=& g(i, 0)
\end{eqnarray}

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[200000];

int solve(int n) {
    int f[n][2];
    int g[n][2];
    for(int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            g[i][j] = n;
            f[i][j] = n;
        }
    }
    if (a[0]) {
        f[0][0] = 1;
    } else {
        f[0][0] = 0;
    }
    for (int i = 0; i < n - 1; i++) {
        f[i + 1][0] = min(g[i][0], g[i][1]) + a[i + 1];
        f[i + 1][1] = f[i][0] + a[i + 1];
        g[i + 1][0] = min(f[i][0], f[i][1]);
        g[i + 1][1] = g[i][0];
    }
    int best = n;
    for (int i = 0; i < 2; i++) {
        best = min(best, f[n - 1][i]);
        best = min(best, g[n - 1][i]);
    }
    return best;
}

int main() {
    int t, n;
    cin >> t;
    int ans[t];
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        if (n == 1) {
            ans[i] = a[0];
        } else {
            ans[i] = solve(n);
        }
        
    }
    for (int i = 0; i < t; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}