题解 | #合唱团#

//逻辑感觉还是有漏洞，但是样例过了
#include<iostream>
#include<vector>
using namespace std;
int s = 0;
void dp(const vector<long long>& a,vector<long long>& v,int k, int d,const vector<bool> &v_b1,vector<bool> &v_b2) {
    if (k == 1) {
        long long t = v[0];
        for (int i = 1; i < v.size(); i++) {
            if (v[i] > t&&v_b2[i]==false) {
                t = v[i];
            }
        }
        cout << t << endl;
        return;
    }
    s++;
    vector<long long> b(v);
    vector<bool> v_b0(v_b2);
    for (int i = s; i < a.size(); i++) {
        long long t = b[i - 1]*a[i];
        int m = i - 1;
        for (int j = i - 2; j >= i - d && j >= s-1; j--) {
            if (t < b[j]*a[i]) {
                t = b[j]*a[i];
                m = j;
            }
        }
        v_b2[i] = v_b0[m] ^ v_b1[i];
        v[i] = t;
    }
    dp(a, v, k - 1, d,v_b1,v_b2);
    return;
}
int main() {
    int n, k, d;
    cin >> n;
    vector<long long> a(n);
    vector<bool> v_b1(n,false);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] < 0)
        {
            v_b1[i] = true;
            a[i] = -a[i];
        }
    }
    vector<bool> v_b2(v_b1);
    vector<long long> v(a);
    cin >> k >> d;
    dp(a, v, k, d,v_b1,v_b2);
    return 0;
}