合唱团问题

系统管理员 2022-03-26 12:07 107阅读 0赞

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

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

解题思路：如果采用暴力解法的话，从n名学生中随机抽取k名学生有![C\_n^k][C_n_k]种取法，对于每一种取法需要计算k次乘法，所以时间复杂度为![O(C\_n^k k)][O_C_n_k k]。这种暴力的解法不能通过，时间复杂度太高，其实做过一些题的应该一开始就能想到用动态规划的方法来做，关键是递推公式怎么写。通过二维数组dp\[n\]\[k + 1\] 来保存获得的乘积，以空间换时间，减少时间复杂度，dp\[i\]\[j\]表示对于每一名同学i，记录他作为选取的k名学生中的第j个所获得的最大乘积。注意到每个学生的能力值会有负值（这是有多差，竟然有负的）。所以，我们需要定义另外一个二维数组来保存最小乘积。通过分析后我们可以用dpmax\[n\]\[k + 1\] 和 dpmin\[n\]\[k +\] 来分别记录最大乘积和最小乘积。然后就可以很容易的得到递推公式：dpmin\[i\]\[j\] = min(dpmin\[i\]\[j\], min(dpmax\[m\]\[j - 1\]\*a\[i\], dpmin\[m\]\[j - 1\]\*a\[i\]))，dpmax\[i\]\[j\] = max(dpmax\[i\]\[j\], max(dpmax\[m\]\[j - 1\]\*a\[i\], dpmin\[m\]\[j - 1\]\*a\[i\]))，这里的m是在i-1到i-d之间。代码如下：

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int main(){
        int n;
        long ans = -50;
        cin >> n;
        vector<int> arr(n, 0);
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        int k;
        int d;
        cin >> k >> d;
        //定义第i个人的作为被选取的第j个学生所得的最大和最小乘积
        vector<vector<long>> dpmax(n, vector<long>(k + 1, 0));
        vector<vector<long>> dpmin(n, vector<long>(k + 1, 1));
        for(int i = 0; i < n; i++){
            dpmax[i][1] = arr[i];
            dpmin[i][1] = arr[i];
        }
        for(int i = 1; i < n; i++){
            for(int j = i - 1; j >= 0 && j >= i - d; j--){
                for(int m = 1; m < k && m <= j + 1; m++){
                   dpmax[i][m + 1] = max(dpmax[i][m + 1], max(dpmax[j][m] * arr[i], dpmin[j] 
                   [m] * arr[i]));
                   dpmin[i][m + 1] = min(dpmin[i][m + 1], min(dpmax[j][m] * arr[i], dpmin[j] 
                   [m] * arr[i]));
                }
            }
        }
        for(int i = 0; i < n; i++){
            ans = max(ans, dpmax[i][k]);
        }
        cout << ans << endl;
        return 0;
    }

可以看出时间复杂度为![\\small O(nkd)][small O_nkd]，比之前的要小，空间复杂度为![\\small O(nk)][small O_nk]。第一篇博客，请大家指正批评！

[C_n_k]: https://private.codecogs.com/gif.latex?C_n%5Ek
[O_C_n_k k]: https://private.codecogs.com/gif.latex?O%28C_n%5Ek%20k%29
[small O_nkd]: https://private.codecogs.com/gif.latex?%5Csmall%20O%28nkd%29
[small O_nk]: https://private.codecogs.com/gif.latex?%5Csmall%20O%28nk%29