题解 | #合唱团#

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
	ll n;
	cin >> n;
	vector<ll>arr(n);//存储每个数
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}

	ll k, d;
	cin >> k >> d;
	vector<vector<ll>>dp1(n + 1, vector<ll>(n + 1, LLONG_MIN));//记录从前i个人中选，第i个人必选，选了j个人时的最大乘积
	vector<vector<ll>>dp2(n + 1, vector<ll>(n + 1, LLONG_MAX));//记录从前i个人中选，第i个人必选，选了j个人时的最小乘积
	//注意，初始化一定要来个正无穷或者负无穷，不能为0
	//否则代码会在有些案例中出错，牛客检测不出来
	//比如
	//2
	//-1 50 
	//2 50
	//初始化为0会打印出0
	//但是正确答案应该为-50

	for (int i = 1; i <= n; ++i)//从前i个人中选
	{
		dp1[i][1] = arr[i - 1];
		dp2[i][1] = arr[i - 1];
		for (int j = 2; j <= k; ++j)//挑选几个人
		{
			if (j > i)//当j > i时，直接退出此次j的循环
			{
				break;
			}
			for (int z = 1; z <= d && (i - z) >= j - 1; z++)//前面挑选的最后一个人
				//i-z代表此次循环选择的那个位置，一定要满足与j不超过d
			{
				dp1[i][j] = max(max(dp1[i - z][j - 1] * arr[i - 1], dp2[i - z][j - 1] * arr[i - 1]), dp1[i][j]);
				dp2[i][j] = min(min(dp2[i - z][j - 1] * arr[i - 1], dp1[i - z][j - 1] * arr[i - 1]), dp2[i][j]);

			}
		}
	}

	ll Max = LLONG_MIN;
	for (int i = k; i <= n; ++i)
	{
		Max = max(Max, dp1[i][k]);
	}

	cout << Max << endl;
	return 0;
}