题解 | #合唱团#

#include <iostream>
#include<vector>
using namespace std;
using i64 = long long;
const int N = 1e3 + 10;

int main() {
    int n, k, d;
    cin >> n ;
    vector<i64> a(n + 1);
    // i64 res =1;
    for (int i = 1; i <= n; i++)cin >> a[i];
    cin>>k>>d;
    vector<vector<i64>> f(n+1,vector<i64>(12,1));
    vector<vector<i64>> g(n+1,vector<i64>(12,1)); 

    // f[1][1] = g[1][1] = a[1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= d; l++) 
            {
                if (a[i] >= 0) {
                    if (i - l >= 0) {
                        f[i][j] = max(f[i][j], f[i-l][j - 1] * a[i]);
                        g[i][j] = min(g[i][j], g[i-l][j - 1] * a[i]);
                    }
                } else if (a[i] < 0) {
                    if (i - l >= 0) {
                        f[i][j] = max(f[i][j], g[i-l][j - 1] * a[i]);
                        g[i][j] = min(g[i][j], f[i-l][j - 1] * a[i]);
                    }
                }

            }
        }
    }

    i64 res = 1;
    for (int i = 1; i <= n; i++) {
        res = max(res, f[i][k]);
    }
    cout << res;
}
// 64 位输出请用 printf("%lld")