2017校招真题在线编程- 网易 合唱团

时间限制：1秒 空间限制：32768K

题目描述

有 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

输出

49

思路：动态规划，DP_MIN[i][j]，DP_MAX[i][j]表示以第i个学生为结尾前i个学生中取到j个值的最小（大）值，这道题由于存在正负数交叉，我这里分别计算了两组

最大最小值，递推关系式为：DP_MIN[j][i] = min(DP_MIN[m][i-1]*students[j-1],DP_MAX[m][i-1]*students[j-1],DP_MIN[j][i]);最大同样。 其中m有取值限制m >= j-d && m >= i-1；
需要注意一些越界问题，比如k个值的乘积不可能在k名学生以前就取到，还有一个测试用例结果超过了INT_MAX所以我这里使用了long long。。。好蛋疼的题目。代码写得也挺丑陋的。。。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
	int num,k,d;
	cin>>num;
	vector<int> students;
	for(int i = 0; i<num; ++i){
        int temp;
        cin>>temp;
        students.push_back(temp);
    }
    cin>>k>>d;
    vector<vector<long long>> DP_MIN(num+1,vector<long long>(k+1,100000));//最大最小初始化
    vector<vector<long long>> DP_MAX(num+1,vector<long long>(k+1,-100000));
    for(int i = 1; i<=num; ++i){       	//以任何一个值结尾并且长度为1的乘积最值都是它本身
    	DP_MIN[i][1] = students[i-1];
    	DP_MAX[i][1] = students[i-1];
    }

    for(int i = 2; i <= k; ++i){	//i这里其实指的是取到的数字数量
        for(int j = i; j <= num ;++j){	//注意j的起始值，k个值的乘积不可能在k名学生以前就取到
            for(int m = j-1; m >= j-d && m >= i-1 ; --m){	//递推关系，注意m取值
                DP_MIN[j][i] = min(DP_MIN[m][i-1]*students[j-1],DP_MIN[j][i]);
                DP_MIN[j][i] = min(DP_MAX[m][i-1]*students[j-1],DP_MIN[j][i]);
                DP_MAX[j][i] = max(DP_MIN[m][i-1]*students[j-1],DP_MAX[j][i]);
                DP_MAX[j][i] = max(DP_MAX[m][i-1]*students[j-1],DP_MAX[j][i]);
            }
        }
    }
    long long res = 0;
    for(int i = k; i <= num; ++i){	//遍历所有长度为k的最值，取得最大值。
        res = max(res,DP_MAX[i][k]);
    }
    cout<<res;
    return 0;
}