牛客-合唱团

发表于 | 分类于 ，

题目

描述

有 n 个学生站成一排，每个学生有一个能力值，
牛牛想从这 n 个学生中按照顺序选取 k 名学生，
要求相邻两个学生的位置编号的差不超过 d，
使得这 k 个学生的能力值的乘积最大，
你能返回最大的乘积吗？

输入

每个输入包含 1 个测试用例。
每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，
表示学生的个数，接下来的一行，包含 n 个整数，
按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。
接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出

输出一行表示最大的乘积。

Example

Input

3
7 4 7
2 50

Output

49

题解

动态规划

  • 定义 minstate(i,j),maxstate(i,j) 为从第 1 到第 j 个学生中选取 i 个学生后得到的乘积的最小与最大值,第 j 个学生必选;
  • 因为能力值可能为负,所以必须维护最大值与最小值;
  • max(maxstate(m,x)) (m =< x <= n) 即为所求
  • 状态转移方程
1
2
3
4
5
minstate(i,j) = |-> min(minstate(i-1,x))*student(i)  ( student(i)>=0 , j-m <= x <=j-1 )
                |-> max(maxstate(i-1,x))*student(i)  ( student(i)<0 , j-m <= x <=j-1 )

maxstate(i,j) = |-> max(maxstate(i-1,x))*student(i)  ( student(i)>=0 , j-m <= x <=j-1 )
                |-> min(minstate(i-1,x))*student(i)  ( student(i)<0 , j-m <= x <=j-1 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>

#define ll long long

using namespace std;

int n,m,k;
ll *student,*minstate,*maxstate;

int main()
{
    int i,j,l,left,right;
    cin>>n;
    student=new ll[n];
    maxstate=new ll[n];
    minstate=new ll[n];
    for(i=0;i<n;++i)
    {
        scanf("%lld",&student[i]);
        minstate[i]=maxstate[i]=student[i];
    }
    cin>>m>>k;
    for(i=1;i<m;++i)
    {
        for(j=n-m+i;j>=i;--j)
        {
            left=max(i-1,j-k),right=j-1;
            maxstate[j]=max(maxstate[j-1]*student[j],minstate[j-1]*student[j]);
            minstate[j]=min(maxstate[j-1]*student[j],minstate[j-1]*student[j]);
            for(int l=right-1;l>=left;--l)
            {
                maxstate[j]=max(maxstate[j],max(maxstate[l]*student[j],minstate[l]*student[j]));
                minstate[j]=min(minstate[j],min(maxstate[l]*student[j],minstate[l]*student[j]));
            }
        }
    }
    ll t=maxstate[n-1];
    for(i=n-2;i>=m;--i)
    {
        if(maxstate[i]>t)t=maxstate[i];
    }
    printf("%lld",t);
    delete[] maxtate,delete[] minstate;
}