蓝桥杯DFS暴力骗分

2018蓝桥杯B组压轴题（DFS骗分）

10.乘积最大
给定N个整数A1, A2, … AN。请你从中选出K个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。

注意，如果X<0， 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
即：0-((0-x) % 1000000009)

【输入格式】
第一行包含两个整数N和K。
以下N行每行一个整数Ai。

对于40%的数据，1 <= K <= N <= 100
对于60%的数据，1 <= K <= 1000
对于100%的数据，1 <= K <= N <= 100000 -100000 <= Ai <= 100000

【输出格式】
一个整数，表示答案。

【输入样例】
5 3
-100000
-10000
2
100000
10000

【输出样例】
999100009

再例如：
【输入样例】
5 3
-100000
-100000
-2
-100000
-100000

【输出样例】
-999999829
 

#include
#define N 1000000009
using namespace std;
typedef long long ll;
int n,k;//n中选k 
ll a[100000];
ll xuan[100000];//选中的k个数 
ll fal_max=1,maxs=-999999999999999999;
int vis[100000];//标记是否选中 void dfs(int step)
{if(step==k){for(int i=0;imaxs)maxs=fal_max;fal_max=1;return ;}for(int i=0;i>n>>k;for(int i=0;i>a[i];dfs(0);if(maxs<0)maxs=0-((0-maxs) % 1000000009);elsemaxs=maxs%N;cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！