問題へのリンク
考察
ある場所より、左まで・右までの最適値でそれぞれ分けて求められないか??
↓
累積和っぽい考え方で求められそう！
Step1:左・右から、それぞれ最適に置き換えた場合の総和を求めていく
イメージは累積和です。
例として、
左から[i]番目までを最適に置き換えた場合の
左から[i]番目までの総和
を求めます。
入力例1です
5 4 3
5 5 0 6 3
左からi個目までの最適な総和を cum_from_left[i]と呼びます
以下では、具体的な値で書いてみます
最初は、cum_from_left[0] = 0ですね
/*
1番目まで最適に置き換えた場合の総和は
min(1番目まで全部置き換えた場合, ひとつ前までの最適値に加算したもの)
となります
*/
cum_from_left[0 + 1] = min(4 * 1, cum_from_left[0] + 数列[0])
/*
2番目も同様です
*/
cum_from_left[1 + 1] = min(4 * 2, cum_from_left[1] + 数列[1])
です。
つまり、抽象化するとこうなります
// i+1番目までの最適な総和は、以下の式で求められます
//
// 私はLですｯ(小声)
// ↓
cum_from_left[i + 1] = min(l * (i + 1), cum_left_from[i] + 数列[i]);これを、左からと右からの両方から行います。
これが必要な前処理です。
Step2:(0 <= i <= n)であるiを全て探索して、最適な分け目を見つけます
あるiで分けた時の最適値 = 左からi個目までの最適値 + 右からn-i個目までの最適値
となるので、その最小値を探します
ACしたコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
const ll INF = 1e18;
int main() {
ll n, l, r;
cin >> n >> l >> r;
vector<ll> vec(n);
for (int i = 0; i < n; i++) cin >> vec[i];
/*
step1:
各i(0<=i<=n)について
左からi個までを最適に書き換えた時の"左からi個目までの総和"を求める
右から(n-i)個までを最適に書き換えた時の"右から(n-i)個目までの総和"を求める
*/
//{左,右}から[i]個目までの総和の最適に操作した時の値
vector<ll> cum_from_left(n + 1, INF);
vector<ll> cum_from_right(n + 1, INF);
cum_from_left[0] = 0;
cum_from_right[0] = 0;
for (int i = 0; i < n; i++) {
//min(i+1個目まで全部書き換えた場合, 書き換えずに追加した場合の値)
cum_from_left[i + 1] = min(l * (i + 1), cum_from_left[i] + vec[i]);
cum_from_right[i + 1] = min(r * (i + 1), cum_from_right[i] + vec[n - i - 1]);
}
/*
step2:
左からi個までを最適に書き換えた時の総和
+
右から(n - i)個までを最適に書き換えた時の総和
が最小になるものを探索する
*/
ll min_sum = INF;
for (int i = 0; i <= n; i++) {
chmin(min_sum, cum_from_left[i] + cum_from_right[n - i]);
}
cout << min_sum;
}
コメント