[蓝桥杯 2018 省 B] 乘积最大
题目描述
给定 N N N 个整数 A 1 , A 2 , ⋯ , A N A_1, A_2,\cdots, A_N A1,A2,⋯,AN。请你从中选出 K K K 个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 1000000009 1000000009（即 1 0 9 + 9 10^9+9 109+9）的余数。
注意，如果 X < 0 X<0 X<0， 我们定义 X X X 除以 1000000009 1000000009 1000000009 的余数是 0 − ( ( 0 − x ) m o d 1000000009 ) 0-((0-x)\bmod 1000000009) 0−((0−x)mod1000000009)。
输入格式
第一行包含两个整数 N N N 和 K K K。
以下 N N N 行每行一个整数 A i A_i Ai。
输出格式
一个整数，表示答案。
样例 #1
样例输入 #1
5 3
-100000
-10000
2
100000
10000
样例输出 #1
999100009
样例 #2
样例输入 #2
5 3
-100000
-100000
-2
-100000
-100000
样例输出 #2
-999999829
提示
对于 40 % 40\% 40% 的数据， 1 ≤ K ≤ N ≤ 100 1\le K\le N\le 100 1≤K≤N≤100。
对于 60 % 60\% 60% 的数据， 1 ≤ K ≤ 1000 1\le K \le 1000 1≤K≤1000。
对于 100 % 100\% 100% 的数据， 1 ≤ K ≤ N ≤ 1 0 5 1\le K\le N\le 10^5 1≤K≤N≤105， − 1 0 5 ≤ A i ≤ 1 0 5 -10^5\le A_i\le 10^5 −105≤Ai≤105。
具体思路
这是一道关于乘积最大化的问题，题目要求从给定的整数中选出K个数，使它们的乘积最大，并将结果除以1000000009后取余数。
我们可以使用动态规划来解决这个问题。设dp[i][j]表示从前i个数中选取j个数乘积的最大值，那么状态转移方程可以表示为： d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ∗ A [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] * A[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−1]∗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]即为所求的乘积最大值的余数。