Codeforces Round #206 (Div. 1) A. Vasya and Robot

問題

codeforces.com

解法

左からいくつの荷物を取るかで全探索します。

左から i 個の荷物を取るとすると, 「連続して同じ手を使うとコストが増える」というのを無視した場合かかるコストは l * (w[0]+w[1]+...+w[i-1]) + r * (w[i]+...+w[n-1]) となります。

で, 連続して同じ手を使わないためにはなるべく交互に手を使えば良いので, そのような戦略を取った際に使うコストを計算します。

これをすべての i について調べて, 最小コストを求めれば良いです。

const int MAXN = 100100;
ll w[MAXN], S[MAXN];
int n;
ll l, r, ql, qr;

// [f, n)
ll getSum(int f) {
    return S[n] - S[f];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> l >> r >> ql >> qr;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    for (int i = 0; i < n; i++) S[i+1] = S[i] + w[i];
    ll ans = 1ll<<55;
    for (int i = 0; i <= n; i++) {
        // [0, i) from left, [i, n) from right
        ll sum = S[i] * l + getSum(i) * r;
        int lcnt = i, rcnt = n-i;
        if (lcnt < rcnt) {
            sum += (rcnt-lcnt-1) * qr;
        } else if (lcnt > rcnt) {
            sum += (lcnt-rcnt-1) * ql;
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}