笔试——Day32

第一题

题目

素数回文

思路

模拟

构建新的数字，判断该数是否为素数

代码

第二题

题目：

活动安排

思路

区间问题的贪⼼：排序，然后分情况讨论

代码

第三题

题目：

合唱团

思路

动态规划

• 状态表示：
  • max_dp[i][j]从[1, i]挑选，挑了j个人，a[i]必选，此时的最大乘积；
  • min_dp[i][j]从[1, i]挑选，挑了j个人，a[i]必选，此时的最小乘积；
• 状态转移方程：

代码

#include <iostream>
#include <vector>

using namespace std;

long long maxProduct(vector<int>& a, int n, int k, int d) {
    vector<vector<long long>> max_dp(n+1, vector<long long>(k+1, LLONG_MIN));
    vector<vector<long long>> min_dp(n+1, vector<long long>(k+1, LLONG_MAX));
    
    // 初始化：只选1个学生的情况
    for (int i = 1; i <= n; ++i) {
        max_dp[i][1] = a[i-1];
        min_dp[i][1] = a[i-1];
    }
    
    for (int j = 2; j <= k; ++j) {
        for (int i = j; i <= n; ++i) {
            // 检查前d个位置
            for (int m = max(i-d, j-1); m < i; ++m) {
                long long temp1 = max_dp[m][j-1] * a[i-1];
                long long temp2 = min_dp[m][j-1] * a[i-1];
                
                max_dp[i][j] = max(max_dp[i][j], max(temp1, temp2));
                min_dp[i][j] = min(min_dp[i][j], min(temp1, temp2));
            }
        }
    }
    
    long long result = LLONG_MIN;
    for (int i = k; i <= n; ++i) {
        result = max(result, max_dp[i][k]);
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int k, d;
    cin >> k >> d;
    
    cout << maxProduct(a, n, k, d) << endl;
    return 0;
}