第一題

題目

素數回文

思路

模擬

構建新的數字，判斷該數是否為素數

代碼

第二題

題目：

活動安排

思路

區間問題的貪?：排序，然后分情況討論

代碼

第三題

題目：

合唱團

思路

動態規劃

• 狀態表示：
  • 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;
}