题解 | 小红的数组操作(hard version) 不用什么搜索

注意到最多加 n-1 次，减 n-1 次，且加减的顺序和位置无所谓，于是枚举加的次数，对每一个模 n 的和求出加到这个值需要的最小代价，然后枚举减的次数，直接从这个表查答案加上减的代价，取最小值即可。

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

using pii = pair<int, int>;

const ll INFLL = 0x3f3f3f3f3f3f3f3fll;

int n;
int p;
int x;
int q;
int y;

ll sum = 0;

vector<ll> dp;

void Solve() {
    cin >> n >> p >> x >> q >> y;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        sum += a;
    }
    dp.assign(n, INFLL);
    for (int i = n - 1; i > -1; i--) {
        dp[(sum + (ll)i * x) % n] = (ll)p * i;
    }
    ll res = INFLL;
    for (int i = 0; i < n; i++) {
        res = min(res, dp[(ll)i * y % n] + (ll)q * i);
    }
    if (res == INFLL) {
        cout << "-1";
        return;
    }
    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}