2017校招真题网易合唱团

- 日理万妓 2022-05-24 00:15 218阅读 0赞

## 题目描述 ##

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

## 输入描述: ##

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

## 输出描述: ##

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

示例1

## 输入 ##

3
    7 4 7
    2 50

## 输出 ##

这道dp很好，划重点！！因为会有负值，所以要开dpmax和dpmin存。

刚开始的时候可以记一下a\[n\]的最大值，k==1的时候可以输出。

记得开longlong，不然只能过50%...

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    long long a[55],dpmax[55][55],dpmin[55][55];
    int main()
    {
    	long long n,k,d,i,j,r,ans=-inf;
    	scanf("%lld",&n);
    	for(i=1;i<=n;i++)
    	{
    		scanf("%lld",&a[i]);
    		dpmax[i][0]=1;
    		dpmin[i][0]=1;
    	} 
    	scanf("%lld%lld",&k,&d);
    	int mxx=-100;//k=1;
    	for(i=1;i<=n;i++)
    	{
    		dpmax[i][1]=a[i];
    		dpmin[i][1]=a[i];
    		if(k==1)
    		{
    			if(a[i]>mxx)
    			mxx=a[i];
    		}
    		for(j=2;j<=k;j++)
      		{
                dpmax[i][j]=-inf;
                dpmin[i][j]=inf;
            }
    	}
    	for(i=1;i<=n;i++)
    	{
    		for(j=2;j<=k;j++)
    		{
    			for(r=i-1;r>=max((long long)1,(i-d))&&r>=j-1;r--)
    			{
    				dpmax[i][j]=max(dpmax[i][j],dpmax[r][j-1]*a[i]);
    				dpmax[i][j]=max(dpmax[i][j],dpmin[r][j-1]*a[i]);
    				dpmin[i][j]=min(dpmin[i][j],dpmin[r][j-1]*a[i]);
    				dpmin[i][j]=min(dpmin[i][j],dpmax[r][j-1]*a[i]);
    				if(j==k)
    				ans=max(ans,dpmax[i][j]);
    			}
    		}
    	}
    	if(k==1)
    	ans=mxx;
    	printf("%lld\n",ans);
    }