[蓝桥杯 2018 省 B] 乘积最大

题目描述

给定 $N$ 个整数 $A_1,A_2,\cdots ,A_N$。请你从中选出 $K$ 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$（即 $10^9+9$）的余数。

注意，如果 $X<0$， 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\mathrm{mod}1000000009)$。

输入格式

第一行包含两个整数 $N$ 和 $K$。

以下 $N$ 行每行一个整数 $A_i$。

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

5 3 
-100000   
-10000   
2   
100000  
10000

样例输出 #1

999100009

样例 #2

样例输入 #2

5 3 
-100000   
-100000   
-2   
-100000  
-100000

样例输出 #2

-999999829

提示

对于 $40\%$ 的数据，$1\le K\le N\le 100$。

对于 $60\%$ 的数据，$1\le K\le 1000$。

对于 $100\%$ 的数据，$1\le K\le N\le 10^5$，$-10^5\le A_i\le 10^5$。

---

具体思路

这是一道关于乘积最大化的问题，题目要求从给定的整数中选出K个数，使它们的乘积最大，并将结果除以1000000009后取余数。

我们可以使用动态规划来解决这个问题。设dp[i][j]表示从前i个数中选取j个数乘积的最大值，那么状态转移方程可以表示为：$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]\ast A[i])$其中A[i]表示第i个数。

根据题目要求，如果乘积结果小于0，则需要计算其除以1000000009的余数。

---

下面是使用C++实现的代码：

#include<bits/stdc++.h>
#define int long long 
#define mod 1000000009
using namespace std;int n, k, a[100005], ans;signed main()
{cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a + 1, a + n + 1);ans = k & 1 ? a[n] : 1;n -= k & 1;k -= k & 1;int l = 1, r = n, f = ans < 0 ? -1 : 1;while (k) {int p = a[l] * a[l + 1], q = a[r] * a[r - 1]; if (p * f > q * f) { ans = (p % mod * ans) % mod;l += 2;} else {ans = (q % mod * ans) % mod;r -= 2;}k -= 2;}cout << ans << endl;return 0;
}

该代码使用二维数组dp来保存中间结果，时间复杂度为O(NK)。最终输出dp[N][K]即为所求的乘积最大值的余数。