笔试——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;
}