当前位置: 首页 > article >正文

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

[蓝桥杯 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((0x)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 1KN100

对于 60 % 60\% 60% 的数据, 1 ≤ K ≤ 1000 1\le K \le 1000 1K1000

对于 100 % 100\% 100% 的数据, 1 ≤ K ≤ N ≤ 1 0 5 1\le K\le N\le 10^5 1KN105 − 1 0 5 ≤ A i ≤ 1 0 5 -10^5\le A_i\le 10^5 105Ai105


具体思路

这是一道关于乘积最大化的问题,题目要求从给定的整数中选出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[i1][j],dp[i1][j1]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]即为所求的乘积最大值的余数。


http://www.kler.cn/a/371409.html

相关文章:

  • 【51 Pandas+Pyecharts | 深圳市共享单车数据分析可视化】
  • Nginx配置基于端口的 Web 服务器
  • kotlin的this和it用法
  • CSS.导入方式
  • 微信小游戏function signature mismatch,RuntimeError: function signature mismatch
  • NVR批量管理软件/平台EasyNVR多个NVR同时管理支持UDP和TCP传输协议
  • 配置mysql 主主模式 GTID
  • SpringBoot篇(运维实用篇 - 日志)
  • CentOS 系统刷新 DNS,解析
  • Visual Studio 字符集设置与文件编码的区别
  • 学习力体系
  • 【Python】爬虫程序打包成exe
  • Markdown 链接
  • view design之table自定义单元格模版
  • 开源一款基于 JAVA 的仓库管理系统,支持三方物流和厂内物流,包含 PDA 和 WEB 端的源码
  • linux 查看磁盘和内存的使用情况
  • springboot+iotdb的应用
  • Redis设计与实现 学习笔记 第十二章 事件
  • MySQL安装配置教程
  • 【数据仓库】
  • uniapp圆形波浪进度效果
  • 2024护理类科技核心期刊汇总(最新版)
  • 基于uniapp微信小程序的宠物救助宠物领养系统
  • 【动植物毒性数据集】毒蛇识别 蘑菇毒性分类 人工智能 深度学习 目标检测 Python(含数据集)
  • 【算法篇】图论类(1)(笔记)
  • 【C#】编写计算机选课程序