Submission #48976164

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = (1 << 30) - 1;

#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    vector<int> T(N);
    for(int i = 1; i < N; i++) cin >> T[i];

    // dp[j][k] := i 番目までみたとき, 先攻が j 個得ており, 直前は k が得たときのコストの最小値
    // k = 0: 先攻, k = 1: 後攻
    vector dp(N / 2 + 1, vector<int>(2, INF));
    dp[0][0] = 0;
    for(int i = 0; i < N; i++){
        vector nx(N / 2 + 1, vector<int>(2, INF));
        for(int j = 0; j < min(i + 1, N / 2); j++){
            // 切らないとき
            nx[j + 1][0] = min(nx[j + 1][0], dp[j][0]);
            nx[j][1] = min(nx[j][1], dp[j][1]);
            // 切るとき
            nx[j][1] = min(nx[j][1], dp[j][0] + T[i]);
            nx[j + 1][0] = min(nx[j + 1][0], dp[j][1] + T[i]);
        }
        swap(dp, nx);
    }

    int ans = min(dp[N / 2][0], dp[N / 2][1]);
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result