题解 | 合唱团

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long solve(vector<int>& ability, int k, int d) {
        int n = ability.size();
        vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(k + 1, vector<long long>(2)));
        
        // 初始化：选择一个学生的情况
        for (int i = 0; i < n; i++) {
            dp[i][1][0] = dp[i][1][1] = ability[i];
            for (int j = 2; j <= k; j++) {
                dp[i][j][0] = LLONG_MAX;
                dp[i][j][1] = LLONG_MIN;
            }
        }
        
        // 遍历选择的学生数量
        for (int j = 2; j <= k; j++) {
            for (int i = j-1; i < n; i++) {
                for (int p = max(0, i - d); p < i; p++) {
                    long long v1 = dp[p][j-1][0] * ability[i];
                    long long v2 = dp[p][j-1][1] * ability[i];
                    if (dp[p][j-1][0] != LLONG_MAX && dp[p][j-1][1] != LLONG_MIN) {
                        dp[i][j][0] = min(dp[i][j][0], min(v1, v2));
                        dp[i][j][1] = max(dp[i][j][1], max(v1, v2));
                    }
                }
            }
        }
        
        long long result = LLONG_MIN;
        for (int i = k-1; i < n; i++) {
            if (dp[i][k][1] != LLONG_MIN) {
                result = max(result, dp[i][k][1]);
            }
        }
        return result;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<int> ability(n);
    for (int i = 0; i < n; i++) {
        cin >> ability[i];
    }
    
    int k, d;
    cin >> k >> d;
    
    Solution solution;
    cout << solution.solve(ability, k, d) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public long solve(int[] ability, int k, int d) {
            int n = ability.length;
            long[][][] dp = new long[n][k + 1][2];
            
            // 初始化
            for (int i = 0; i < n; i++) {
                for (int j = 0; j <= k; j++) {
                    dp[i][j][0] = Long.MAX_VALUE;
                    dp[i][j][1] = Long.MIN_VALUE;
                }
                dp[i][1][0] = dp[i][1][1] = ability[i];
            }
            
            // 遍历选择的学生数量
            for (int j = 2; j <= k; j++) {
                for (int i = j-1; i < n; i++) {
                    for (int p = Math.max(0, i - d); p < i; p++) {
                        long v1 = dp[p][j-1][0] * ability[i];
                        long v2 = dp[p][j-1][1] * ability[i];
                        if (dp[p][j-1][0] != Long.MAX_VALUE && dp[p][j-1][1] != Long.MIN_VALUE) {
                            dp[i][j][0] = Math.min(dp[i][j][0], Math.min(v1, v2));
                            dp[i][j][1] = Math.max(dp[i][j][1], Math.max(v1, v2));
                        }
                    }
                }
            }
            
            long result = Long.MIN_VALUE;
            for (int i = k-1; i < n; i++) {
                if (dp[i][k][1] != Long.MIN_VALUE) {
                    result = Math.max(result, dp[i][k][1]);
                }
            }
            return result;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] ability = new int[n];
        for (int i = 0; i < n; i++) {
            ability[i] = sc.nextInt();
        }
        
        int k = sc.nextInt();
        int d = sc.nextInt();
        
        Solution solution = new Solution();
        System.out.println(solution.solve(ability, k, d));
        
        sc.close();
    }
}

class Solution:
    def solve(self, ability: List[int], k: int, d: int) -> int:
        n = len(ability)
        dp = [[[float('inf'), float('-inf')] for _ in range(k + 1)] for _ in range(n)]
        
        # 初始化：选择一个学生的情况
        for i in range(n):
            dp[i][1][0] = dp[i][1][1] = ability[i]
        
        # 遍历选择的学生数量
        for j in range(2, k + 1):
            for i in range(j-1, n):
                for p in range(max(0, i - d), i):
                    v1 = dp[p][j-1][0] * ability[i]
                    v2 = dp[p][j-1][1] * ability[i]
                    if dp[p][j-1][0] != float('inf') and dp[p][j-1][1] != float('-inf'):
                        dp[i][j][0] = min(dp[i][j][0], min(v1, v2))
                        dp[i][j][1] = max(dp[i][j][1], max(v1, v2))
        
        result = float('-inf')
        for i in range(k-1, n):
            if dp[i][k][1] != float('-inf'):
                result = max(result, dp[i][k][1])
        return result

# 读取输入
n = int(input())
ability = list(map(int, input().split()))
k, d = map(int, input().split())

solution = Solution()
print(solution.solve(ability, k, d))