合唱团 (线性dp)

时间：2021-10-21 08:00:47

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

思路：表示在i个位置选了j人的最大乘积，表示在i个位置选了j人的最小乘积。为什么要记录最小乘积？因为每个学生的能力值可能为正可能为负，那么必须保存最小乘积，才能保证不遗漏负数相乘的情况。

AC代码

#include <stdio.h>
#include <algorithm>
using namespace std;
#define inf 1e14
typedef long long LL;
typedef pair<LL, LL> pii;
const int maxn = 50+5;
//d(i, j, 1)表示在i个位置选了j人的最大乘积
//d(i, j, 1)表示在i个位置选了j人的最小乘积
LL dp[maxn][15][2];
int a[maxn];

int main() {
    int n, cnt, d;
    while(scanf("%d", &n) == 1) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            dp[i][1][1] = dp[i][1][0] = a[i];
        }
        scanf("%d%d", &cnt ,&d);
        for(int i = 1; i <= n; i++) {
            for(int j = 2; j <= min(cnt, i); j++) {
                dp[i][j][1] = -inf,
                dp[i][j][0] = inf;
                for(int k = i-1; k > 0 && k >= i-d && k >= j-1; k--) {
                    for(int q = 0; q < 2; q++) {
                        dp[i][j][1] = max(dp[i][j][1], dp[k][j-1][q] * a[i]);
                        dp[i][j][0] = min(dp[i][j][0], dp[k][j-1][q] * a[i]);
                    }
                }
            }
        }

        LL ans = -inf;
        for(int i = cnt; i <= n; i++) {
            ans = max(ans, dp[i][cnt][1]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

如有不当之处欢迎指出！

相关文章