Jimy Ma's Zone
0%

网易2017内推笔试题-合唱团

Posted on In ,

合唱团

题目描述

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

输入描述

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

输出描述

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

解法分析

这道题最笨的方法也是最容易想到的方法就是遍历.
也就是说,把所有可能的tuple都试一遍.
把tuple中所有数乘积最大的数输出出来就好了.

在不考虑时间和空间复杂度的情况下,所谓一力降十会. 用遍历方法可以解决所有的决策问题. 然而不管是在笔试题当中还是在实际的应用中(比如在编码领域).那么遍历方法可以说是噩梦级的存在了.该题若采用遍历的算法,在给定的空间复杂度的要求之下,AC rate为80%.

这个题的正解是采用动态规划的算法.表面上看是一个很高端的名词,其实就好比走路. 下一步的捷径可以通过前一步或者前几步的捷径递推得到.

通过这个题,也看出了遍历在动态规划的面前有多么的苍白无力.只用了相对于遍历而言很少的内存和时间就可以得到最优解.

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;
int main() {
    int n;
    cin >> n;
    int data[n];
    for(int i =0; i < n; i++)
    {
        cin >> data[i];
    }
    int k, d;
    cin >> k >> d;

    //因为有正负值,所以要分别存储最大值和最小值.
    long int maxvalue[n][k];
    long int minvalue[n][k];
    for(int i =0; i < n; i++)
    {
        for(int j = 0; j < k; j++)
        {
            maxvalue[i][j] = LONG_MIN;
            minvalue[i][j] = LONG_MAX;
        }
    }
    long int res = LONG_MIN;

    for(int i = 0; i < n; i++)
    {
        maxvalue[i][0] = minvalue[i][0] = data[i];
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= min(i, k-1); j++)
        {
            //请注意,这里l >= max(0, max(i - d, j-1))是为了保证不会访问到非法的索引,这也是一个难点.
            for(int l = i-1; l >= max(0, max(i - d, j-1)); l--)
            {
                //递推表达式,动态规划的难点.
                maxvalue[i][j] = max(maxvalue[i][j],
                                     max(maxvalue[l][j-1] * data[i],
                                         minvalue[l][j-1] * data[i]));
                minvalue[i][j] = min(minvalue[i][j],
                                     min(maxvalue[l][j-1] * data[i],
                                         minvalue[l][j-1] * data[i]));
            }
        }
    }
    for(int i = k-1; i < n; i++)
    {
        res = max(res, maxvalue[i][k-1]);
    }
    cout << res;
}